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.
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.
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:
1 2
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:
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.
I did not look up the Sieve, but something in that code looks a bit odd.
@Aceix:
1 2 3 4
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.
1 2 3 4
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[.