Archive

Posts Tagged ‘prime optimization’

Sieve of Eratosthenes CPP source code


Seive of Eratosthenes is one of the mostly used prime generation algorithms.
Algorithm is very simple and straight forward.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:
1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked; let p now equal this number (which is the next prime).
5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.
When the algorithm terminates, all the numbers in the list that are not marked are prime.

Improvements over Seives of Eristhones:
One of the improvements that can reduce the larger computation is not including 2’s multiples (however, the only even and prime number is 2). Just considering only the odd numbers we can reduce prime holding array size and improve performance.

The following C++ uses the above improvement and considers each element of primes array as an odd number i.e. primes[n] represents 2*n+1 number in real. At the end of the operation primes array will have one’s in all the corresponding indices of prime numbers.

The below code can be seen running using ideone online compiler

// Written by Vasanth Raja Chittampally
// Source Code: Sieve of Eratosthenes
// All rights are reserved
#include #include
#include
void seive(int start, int range, int * primes)
{
//Seiving is done here
long start1 = clock();
for(int i = 6; i {

int iter = 2 * i + 1;
if(primes[i] == 1)
{
int startInLoop = start / iter;
if(startInLoop % 2 == 0)
startInLoop++;
if(startInLoop < 13)
startInLoop = 13;
for(int j = startInLoop * iter; j primes[(j - 1) / 2] = 0;
}
}
std::cout< int count = 0;
// display the results
for(int i = start / 2; i if(primes[i] != 0)
{
//std::cout<< 2 * i + 1 << " ";
count++;
}
std::cout< }
int main(void)
{
const int range = 5000000 ;

const int start = 1000000 ;
int * primes = new int[range / 2 + 1];
long time1 = clock();
for(int i = 0; i {
primes[i] = 1;
}
for(int i = 4; i {
primes[i] = 0;
}
for(int i = 7; i {
primes[i] = 0;
}
for(int i = 10; i {
primes[i] = 0;
}
for(int i = 16; i {
primes[i] = 0;
}
long totTime = clock() - time1;
std:: cout << std::endl< return 0;
}

The above code can be seen running using ideone online compiler

Advertisements

What is the sum of all primes below two millions?


The idea to minimize the amount of time is that, if a number has factors other than 1 and itself must exist between 2 and square root of that number.

The above constraint reduces innumerable number of comparisons and saves a lot of space too.

Here is the code to find the sum of all primes below two millions.

<blockquote>package projecteuler;

/**
*
* @author Vasanth Raja Chittampally
*/
public class ProjectEuler {

public static void main(String[] args) {
long sum=2;
out: for (long i = 3; i &lt; 2000000; i++) {
if(i%2==0)
continue out;
for (int j = 3; j &lt;=Math.sqrt(i); j+=2) {
if(i%j==0) continue out;
}
sum+=i;

}
System.out.println(""+sum);
}</blockquote>