can anyone code this...........

Write a C++ program of the following problem:
How many numbers are there below one-billion (109) that has only one or two Prime Factor.
closed account (48T7M4Gy)
Checkout 'Sieve of Eratosthenes'
I can't understand what the program should do actually
Please be more specifically
Last edited on
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.

PS kemort, great resource. Thank you.
Last edited on
1
2
3
4
5
6
7
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] );
      else
         break;
Last edited on
closed account (48T7M4Gy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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 = new int[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. :)
Topic archived. No new replies allowed.