stuck on 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.
"j" is used for indexing vector prime.


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();

}

[keskiverto]

Start by assuming that i is a prime. bool found = true;

If you do find in iteration a previous prime that can divide i, then found = false; and you can abort iteration.

After iteration true == found only if no known prime could divide i. In that case i is a prime and should be added to the list.

[Zaita]

See the box labelled "search" at the top? Type 'prime numbers' in to it and press 'Go'. This question has been answered 100x before with more than enough code for you to complete your homework.

[Chervil]

In order for the number i to be prime, this loop must process each and every element of the vector, for (j=0; j<prime.size(); j++)

There are two cases to consider. If the number can be divided by any element, just break out of the loop:

    if (i%prime[j] == 0)
        break;

The other case is where the loop proceeds all the way to the end without executing the break statement. You can check for that by testing the value of j after the loop terminates:

    if (j == prime.size())
        prime.push_back(i);

[dhruv90]

@Zaita , this ain't my homework and if you don't wish to answer something, you don't need to!! :)

[dhruv90]

Thanks a lot for ur replies

[Aceix]

Whatabout this technique?

int iFactors=0,num;
cout<<"Enter a number: ";
cin>>num;

for(int i=1;i<=num;i++)
if(num%i==0)
iFactor++;

if(iFactor==2)
cout<<"\nNumber is prime";

Aceix.

[dhruv90]

@Aceix are u trying to enter an number, and then tellin whether its prime or not. Or are you tryin to find all prime numbers till num.

[Aceix]

telling whether a number is prime or not. didn't read. sorry

Aceix.

[dhruv90]

sorry, abt before

this works fine.
It's a cool way actually.

[Aceix]

dhruv90 wrote:

umm.. this code doesn't compiles!!

mine? it is not complete. you must add the main function, header file(s) and use the std namespace.

if u enter the num=6
how will that work

it would init i=1, check if when 1 enters into 6, there is a remainder of 0. if positive, then iFactor++. then i++(i=2) also checks if i(2) enters 6 with a remainder of 0.
It does this until i>num(6), then checks if iFactor=2(ie: for a prime number) since prime numbers have two factors.

Aceix.

[dhruv90]

another cool way to display primes till a given n;

(Sieve of Eratosthenes)


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

using namespace std;

int main()
{
int max=0;
int i=0,j=0;

cout<<"Please enter the max. no. till which you want to calculate the primes \n";
cin>>max;

vector<int>prime(max,1);

for(i=2;i*i<=max;i++)
{
if(prime[i]==1)
{
for(j=2;j<=max;j+=2)
{
prime[j+2] = 0;
}
}
}

for(i=2;i<=max;i++)
{
if(prime[i]==1)
cout<<i<<endl;
}





getch();

}

[keskiverto]

I did not look up the Sieve, but something in that code looks a bit odd.

@Aceix:

int iFactor = 0;
for ( int i=1; i<=num; i++)
  if ( num%i==0 )
    iFactor++;

This seems a bit redundant. We know that 1 and num can divide. There is no point testing them.

for ( int i=2; i<num; ++i )
  if ( 0 == num%i )
    ++iFactor;
// assert: num is prime IIF iFactor==0 

However, even that is too much, because for every odd number 0==num%2 and looping to num-1 with them would be waste of time, same applies to most non-primes.

The algorithm in OP had extra leverage: it did solve the previous primes too, so it could reduce the loop range
from for each i in [2..num[ to for each prime in [2..num[.

[Zaita]

As I said, search for prime numbers in the forums there are many pieces of code already available to do this.

e.g. http://www.cplusplus.com/forum/beginner/98616/

[eyenrique]

http://www.cplusplus.com/forum/beginner/101355/