help, trying to find prime number

ok, i just started working with c++, and im doing a basic project trying to find all the prime numbers under 100.

here is what i have right now:

Code:

---

/*variables needed num1, num2, index.
if num1 % num2 = 0 index++, if index = 0 print num1. */
#include <iostream>
using namespace std;

int main ()
{
        int num1, num2;// the 2 numbers we divide to find the remainder
        int remainder, index=0; // remainder determines if the number is prime or not

        for(num1=1; num1 <= 100; num1++) // we take each number under 100
        {
                index = 0;// we reset index back to 0
                for(num2=1; num2< num1; num2++) //and mod it be each number lower than itself
                {
                        remainder = num1%num2; // find out the remainder of it
                        if(remainder != 0) // and if there is none
                        {
                                index++; // we increment index once.
                        }
                }
                if (index != 0) // if we didnt increment index during that operation
                {       
                        cout << num1 << " is a prime number\n"; // it means that num1 is a prime number
                }
        }
        cin.get();
        return 0;
}

---

issue is, i get 77-100 as prime numbers, nothing before 77 at all, and not only the prime numbers between 77 and 100, but rather 77, 78, 79, 80, etc.

i know i probably made a logic error somewhere along the line.

can someone please look through the code tell me where im wrong. because ive been staring at it for an hour w/ no luck so far.

if (index != 0) // if we didnt increment index during that operation


Comment doesn't match the code here.

Quote:

---

Originally Posted by KCfromNC

if (index != 0) // if we didnt increment index during that operation


Comment doesn't match the code here.

---

hmm, thats cuz i messed w/ it a lot before finally posting here.


i still have the problem tho, i tried lowering my range to 100 and i get 3-10 as prime numbers, when clearly numbers like 4, and 6 are not, and 1-3 nothing shows. im still confused.


here is what i have, yet again.

Code:

---

/*variables needed num1, num2, index.
if num1 % num2 = 0 index++, if index = 0 print num1. */
#include <iostream>
using namespace std;

int main ()
{
        int num1, num2;// the 2 numbers we divide to find the remainder
        int remainder=0, index=0; // remainder determines if the number is prime or not

        for(num1=1; num1 <= 10; num1++) // we take each number under 100
        {
                cout << "after first for loop num1 is " << num1 <<endl;
                cout << "after first for loop index is " << index <<endl;
                index = 0;// we reset index back to 0
                for(num2=1; num2<num1; num2++) //and mod it be each number lower than itself
                {
                        remainder = num1%num2; // find out the remainder of it
                        cout << "after second for loop num2 is " << num2 << endl;
                        cout << "after second for loop remainder is: " << remainder << endl;               
                        if(remainder == 0) // and if there is none
                        {
                                ++index; // we increment index once.
                        cout << "after first if index is " << index <<endl;
                        }
                }
                if (index == 0) // if we didnt increment index during that operation
                {       
                        cout << "after second if num1 is " << num1 <<endl;
                        cout << "after second if index is " << index <<endl;
                        cout << "after second if num2 is " << num2 << endl;
                        cout << "after second if remainder is: " << remainder << endl;
                        cout << num1 << " is a prime number\n\n\n"; // it means that num1 is a prime number
                }
        }
        cin.get();
        return 0;

---

still havent gotten it to work, i have cout statements there because i want to see where the issue is, none of the couts from if(index == o) ever print for a range from 1-10. so im confused why that is.


thats the source code, here is the output:

Code:

---

after second for loop remainder is: 0

after first if index is 1

after first for loop num1 is 3
after first for loop index is 1

after second for loop num2 is 1
after second for loop remainder is: 0

after first if index is 1

after second for loop num2 is 2
after second for loop remainder is: 1

after first for loop num1 is 4
after first for loop index is 1

after second for loop num2 is 1
after second for loop remainder is: 0

after first if index is 1

after second for loop num2 is 2
after second for loop remainder is: 0

after first if index is 2

after second for loop num2 is 3
after second for loop remainder is: 1

after first for loop num1 is 5
after first for loop index is 2

after second for loop num2 is 1
after second for loop remainder is: 0

after first if index is 1

after second for loop num2 is 2
after second for loop remainder is: 1

after second for loop num2 is 3
after second for loop remainder is: 2

after second for loop num2 is 4
after second for loop remainder is: 1

after first for loop num1 is 6
after first for loop index is 1

after second for loop num2 is 1
after second for loop remainder is: 0

after first if index is 1

after second for loop num2 is 2
after second for loop remainder is: 0

after first if index is 2

after second for loop num2 is 3
after second for loop remainder is: 0

after first if index is 3

after second for loop num2 is 4
after second for loop remainder is: 2

after second for loop num2 is 5
after second for loop remainder is: 1

after first for loop num1 is 7
after first for loop index is 3

after second for loop num2 is 1
after second for loop remainder is: 0

after first if index is 1

after second for loop num2 is 2
after second for loop remainder is: 1

after second for loop num2 is 3
after second for loop remainder is: 1

after second for loop num2 is 4
after second for loop remainder is: 3

after second for loop num2 is 5
after second for loop remainder is: 2

after second for loop num2 is 6
after second for loop remainder is: 1

after first for loop num1 is 8
after first for loop index is 1

after second for loop num2 is 1
after second for loop remainder is: 0

after first if index is 1

after second for loop num2 is 2
after second for loop remainder is: 0

after first if index is 2

after second for loop num2 is 3
after second for loop remainder is: 2

after second for loop num2 is 4
after second for loop remainder is: 0

after first if index is 3

after second for loop num2 is 5
after second for loop remainder is: 3

after second for loop num2 is 6
after second for loop remainder is: 2

after second for loop num2 is 7
after second for loop remainder is: 1

after first for loop num1 is 9
after first for loop index is 3

after second for loop num2 is 1
after second for loop remainder is: 0

after first if index is 1

after second for loop num2 is 2
after second for loop remainder is: 1

after second for loop num2 is 3
after second for loop remainder is: 0

after first if index is 2

after second for loop num2 is 4
after second for loop remainder is: 1

after second for loop num2 is 5
after second for loop remainder is: 4

after second for loop num2 is 6
after second for loop remainder is: 3

after second for loop num2 is 7
after second for loop remainder is: 2

after second for loop num2 is 8
after second for loop remainder is: 1

after first for loop num1 is 10
after first for loop index is 2

after second for loop num2 is 1
after second for loop remainder is: 0

after first if index is 1

after second for loop num2 is 2
after second for loop remainder is: 0

after first if index is 2

after second for loop num2 is 3
after second for loop remainder is: 1

after second for loop num2 is 4
after second for loop remainder is: 2

after second for loop num2 is 5
after second for loop remainder is: 0

after first if index is 3

after second for loop num2 is 6
after second for loop remainder is: 4

after second for loop num2 is 7
after second for loop remainder is: 3

after second for loop num2 is 8
after second for loop remainder is: 2

after second for loop num2 is 9
after second for loop remainder is: 1

---

I guess your problem is that all numbers are divisible by 1.

Quote:

---

Originally Posted by anon

I guess your problem is that all numbers are divisible by 1.

---

that was kinda it. i changed it so if index is 1 its a prime number, and it comes out with

2
3
5
7

so i need to figure out a way to exclude 2 and im good.


wait, 2 is a prime number right? its divisible by 1 and 2 only. so i guess its working fine now. i think.


AWESOME it works, thats great, thank you for the help. im off to find the next prime number now.

Quote:

---

Originally Posted by vampirekid.13

so i need to figure out a way to exclude 2 and im good.

---

But 2 is a prime number.

Quote:

---

Originally Posted by laserlight

But 2 is a prime number.

---

yea, i realized that shortly after making myself look stupid on a public c++ board. heh.


also now i need to find a way to include 1 in all of it, but im lazy and i think im just going ot hardcode it in and not worry about it.

you could count how many times the remainder was 0

If it's more than 2 then it's not a prime number

Quote:

---

Originally Posted by ಠ_ಠ

you could count how many times the remainder was 0

If it's more than 2 then it's not a prime number

---

yea, thats what i ended up doing. and it worked, im runing it now trying to find all the prime numbers less than 4billion haha :D


i kinda regret not saving them to a file or anything, but im doing it just for fun anyway.


its been a few hrs now, i am @ 1 million....i got a long time left to go.

Quote:

---

Originally Posted by vampirekid.13

yea, thats what i ended up doing. and it worked, im runing it now trying to find all the prime numbers less than 4billion haha :D


i kinda regret not saving them to a file or anything, but im doing it just for fun anyway.


its been a few hrs now, i am @ 1 million....i got a long time left to go.

---

That's horridly slow.
You could stop it, make a few improvements and run it again, and have it catch up to where is was in less than 30 seconds.

I agree with iMalc.

You could try implementing The Sieve of Eratosthenes to make it a lot faster. Although it will also use a lot more memory.

My time for primes from 2 to 1 Million is about 2.6 secs. ('real' return value from the 'time' command).

To improve your speed, you can, for example:
- break out of the inner loop when remainder == 0, instead of further looping;
- calculate num2 up to sqrt(num1);
- skip the even numbers in the outer (and inner) loops, they won't be primes anyway.

Quote:

---

Originally Posted by Ideswa

My time for primes from 2 to 1 Million is about 2.6 secs. ('real' return value from the 'time' command).

---

Interesting. I just tested my "perfect" trial division submission to our prime number generation contest, and my program found the primes less than 1 million in the order of 0.2 seconds. So, it is either a case of my computer being much faster than yours, or "perfect" trial division with primes really is so much faster than trial division with odd numbers. (Or both.)

Nice! I haven't used any of the fast prime algorithms yet. But I'm having a lack of time because I have my final exams in 17 days and I have to code some PHP websites too :p.

hmm... there might be another reason: did you print out all the primes found? When I changed my implementation to do that (since that is what vampirekid.13 did, after all), the time taken was in the neighbourhood of 2.25 seconds.

Yeah, I printf() them. Without printing it's 1.8 secs. I have looked into wikipedia on Trial division - Wikipedia, the free encyclopedia, is that the algorithm you use? That is just the "brute force" one right? Then what is perfect to it?

Quote:

---

Originally Posted by Ideswa

I have looked into wikipedia on Trial division - Wikipedia, the free encyclopedia, is that the algorithm you use?

---

Yes, which is pretty much the same as what you used. I call it "perfect" because it only uses primes as trial divisors.

The sieve of Eratosthenes is likely to be much faster and yet feasible in this case of just finding the primes less than one million.

The sieve is memory-heavy though?
So you store primes in an array or something and when you check integer 'n' for primality you check if 'n mod x' != 0 where x are only primes you calculated before?

Edit: I now store validated primes in an array and only use the modulus with the primes in that array. Time without printf() now is 0.7 secs for integers up to 1 million.

Quote:

---

Originally Posted by Ideswa

The sieve is memory-heavy though?

---

Assuming CHAR_BIT is 8, you could store a million bits in 125000 bytes. But even if you use ints instead (bools would be most natural option), that would still be less than sizeof(int) megabytes of memory needed, which should fit on the stack too.

Quote:

---

Originally Posted by Ideswa

So you store primes in an array or something and when you check integer 'n' for primality you check if 'n mod x' != 0 where x are only primes you calculated before?

---

Yes, up to the square root of the candidate number.

Quote:

---

Originally Posted by laserlight

hmm... there might be another reason: did you print out all the primes found? When I changed my implementation to do that (since that is what vampirekid.13 did, after all), the time taken was in the neighbourhood of 2.25 seconds.

---

u guys are a lot more advanced than me however, i just made a quick program because it was a project for my c++ tutorial, i appreciate the great advice and as i get further and learn more ill make it better, but as of right now i dont really know how to "break" out of a loop, i know how to skip the prime numbers tho so i guess i can add that in. but yea, you guys prolly did this for years now, im on my first week.