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.

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.

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.

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.

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

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


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.

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


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.

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 .

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.