Prime number is a number that can be divided evenly only by 1 or itself.
2 is a prime number.
3 is a prime number.
6 on the other hand, is not a prime number since it can be divided by
(besides 1 and itself) 2 and 3.
Conversely, 6 can be obtained by multiplying 3 and 2 together and so
6 is one of the numbers that you are looking for. Coincidentally, 2 and 3
are also numbers that you are looking for because each of them
has only two prime factors.
The simplest thing you could do is write an algorithm that just steps through
a billion of numbers trying to divide each evenly and if it divides evenly more
than once discard it. I bet it will take a long time though...
Try to think back to permutations, combinations, sequences and series etc.
solution = primes; //one prime factor
for(int K=0; K<primes.size(); ++K)
for(int L=K; L<primes.size(); ++L) //L=K+1 if the factors need to be different
if( primes[K]*primes[L] < limit )
solution.push( primes[K]*primes[L] );
elsebreak;
// Generates a list of all +ve numbers < limit, prime = 1, non-prime = 0
int* primeList(int limit)
{
// Create a sieve of integers for the full range
int* sieve = newint[limit];
// Set all elements to prime ( = 1 )
for (int i = 0; i < limit; i++)
sieve[i] = 1;
// NOTE: 1 is not prime so start loops at 2.
// At positions of multiples of i, set value to 1
for ( int i = 2; i <= limit; i++)
{
if (sieve[i] == 1)
{
for (int j = i + i; j < limit; j += i)
sieve[j] = 0;
}
}
sieve[limit] = -1; // terminator
return sieve;
}
This is the sieve in action. If you want to know if n is prime then check the value of sieve[n]. n is prime if sieve[n] = 1. :)