help, trying to find prime number

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 05-01-2009
vampirekid.13
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.
• 05-01-2009
KCfromNC
if (index != 0) // if we didnt increment index during that operation

Comment doesn't match the code here.
• 05-01-2009
vampirekid.13
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```
• 05-01-2009
anon
I guess your problem is that all numbers are divisible by 1.
• 05-01-2009
vampirekid.13
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.
• 05-01-2009
laserlight
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.
• 05-01-2009
vampirekid.13
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.
• 05-01-2009
ಠ_ಠ
you could count how many times the remainder was 0

If it's more than 2 then it's not a prime number
• 05-01-2009
vampirekid.13
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.
• 05-01-2009
iMalc
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.
• 05-02-2009
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.
• 05-02-2009
Ideswa
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.
• 05-02-2009
laserlight
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.)
• 05-02-2009
Ideswa
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.
• 05-02-2009
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.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last