prime numbers

[dhruv90]

So, I am trying to find prime numbers between 1 and 100. I know what prime numbers are. I am using this technique to come up with the prime numbers:

a) I will make a vector of primes, push_back the prime number "2" as the first prime number.

b)Choose an iterator "i", iterate from numbers starting at 3 and ending at 100.

c) To check if a no. is prime or not, I check whether it is divisible by previous stored prime numbers.(So when i start with number-"3", i see if it is divisible by "2",which is my previously stored no.)

d)I am trying to do something like this: i%prime[j]!=0, then store the number.


I do think, this is how the problem should be tackled, but still, I am stuck bad.

Here is my incomplete code.



#include<iostream>
#include<conio.h>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;


int main()
{

vector<int>prime;
int i=0,j=0;

prime.push_back(2);

for(i=3;i<100;i++)
{
for(j=0;j<prime.size();j++)
{
if(i%prime[j]!=0)

//do something

}

}

getch();

}

[abhishekm71]

you are in the right direction. ofcourse it can be made more efficient.
your "// do something" is the actual meat part. try it out yourself.

[dhruv90]

what i can do is,

if(i%prime[j]!=0) //if it holds
prime.push_back(i);

But then if i have a list like this;

2
3
5
7

And if i am trying to check for "9" now,
The above stated code will check for i%2!=0

and push_back(9)
But of course this is wrong(9 is not a prime number)

The thing that i am not being able to achieve, even after thinking a lot is
How to check "i" for each of the stored primes, and then only push_back, and not before.

Need help!!

[abhishekm71]

try this:

for(i=3;i<100;i++)
{
  bool isPrime = 1;   // first assume that the candidate is a prime number.
  for(j=0;j<prime.size();j++)
  {
     if(i%prime[j]==0)
     {
        isPrime = 0;
        break; 
      }
   }
    if (isPrime)
      // now pushback this number to the list of primes vector.
}

Edit: Also, atleast for this purpose you don't need to include the algorithm and string libraries.

[dhruv90]

haha,
thanks a lot. I could never think of this, I am new to c++. Thou could have done this using goto. But i have heard "goto" isn't pretty.

[abhishekm71]

it is a standard pattern of array checking and then prematurely breaking out of the for/while loop. yes it is strongly recommended not to use goto statements because they can result in a highly "volatile"/unwanted/undesired behaviour if the programmer is not careful enough.

Moreover, whatever the goto statement can do can be accomplished more cleanly and simply by other standard loops.

[dhruv90]

cool,will keep this in mind!!