10. Sum of Prime

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.  Find the sum of all the primes below two million.

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.   A natural number greater than 1 that is not a prime number is called a composite number.   For example, 5 is prime, as only 1 and 5 divide it, whereas 6 is composite,   since it has the divisors 2 and 3 in addition to 1 and 6.

import java.util.Arrays;
import java.util.Calendar;

public class Problem10 {
   //natural looping algorithm
    public void primesPE() {
        long l=10000000,sum =5, n=5;
        while(n<=l)  {
            if (isPrime(n)) sum+=n;
            n+=2;
            if (isPrime(n) && n<l)  sum+=n;
            n+=4;
        } 
       System.out.println(sum);
    }

    public boolean isPrime(long n) {
        if(n==1)
            return false;
        else if (n<4)
            return true; //2 and 3 are prime
        else if (n%2==0)
            return false;
        else if (n<9)
            return true; //we have already excluded 4,6 and 8.
        else if (n%3==0)
            return false;
        else {
            double r=Math.floor(Math.sqrt(n)); // n rounded to the greatest integer r so that r*r<=n
            double f=5;
            while(f<=r) {
                if (n%f==0)
                        return false;// (and step out of the function)
                if (n %(f+2)==0)
                    return false; //(and step out of the function)
                f=f+6;
            }
        }
        return true; //(in all other cases)
    }

 //The sieve of Eratosthenes algorithm
/*1. Make a list of all numbers from 2 to N.
2. Find the next number p not yet crossed out. This is a prime. If it is greater than sqrt(N), go to 5.
3. Cross out all multiples of p which are not yet crossed out.
4. Go to 2.
5. The numbers not crossed out are the primes not exceeding N.

/*Example
To find all the prime numbers less than or equal to 30, proceed as follows. First generate a list of integers from 2 to 30:

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

First number in the list is 2; cross out every 2nd number in the list after it (by counting up in increments of 2), i.e. all the multiples of 2:

2  3  x4  5  x6  7  x8  9  x10 11 x12 13 x14 15 x16 17 x18 19 x20 21 x22 23 x24 25 x26 27 x28 29 x30

Next number in the list after 2 is 3; cross out every 3rd number in the list after it (by counting up in increments of 3), i.e. all the multiples of 3:

2  3  x4  5  x6  7  x8  x9  x10 11 x12 13 x14 x15 x16 17 x18 19 x20 x21 x22 23 x24 25 x26 x27 x28 29 x30

Next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after it (by counting up in increments of 5), i.e. all the multiples of 5:

2  3  x4  5  x6  7  x8  x9  x10 11 x12 13 x14 x15 x16 17 x18 19 x20 x21 x22 23 x24 25 x26 x27 x28 29 x30

Next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number in the list after it, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7*7 is greater than 30. The numbers left not crossed out in the list at this point are all the prime numbers below 30:

2  3     5     7           11    13          17    19          23                29
*/

    public void primesPE1() {
        long l=10000000,sum =0;
        //int sb = (int) ((l-1)/2);
        int cl = (int)Math.sqrt((double)l);
        boolean s[] = new boolean[(int)(l+1)];
        Arrays.fill(s, false);
        for (int i=4;i<=l;i=i+2) {
            s[i]=true;
        }
        for (int i=3;i<=cl;i=i+2) {
            if (!s[i]) {
                for (int j=i*i;j<=l;j=j+(2*i)) {
                    s[j]=true;
                }
            }
        }
        for (int i=2;i<=l;i++){
            if(!s[i]) {
                sum=sum+i;
            }
        }
        System.out.println(sum);
    }

    public void primesPE2() {
        long l=10000000,sum =2;
        int sb = (int) ((l-1)/2);
        int cl = (int)(Math.sqrt((double)l)-1)/2;
        boolean s[] = new boolean[sb+1];
        Arrays.fill(s, false);
        for (int i=1;i<=cl;i++) {
            if (!s[i]) {
                for (int j=(2*i*(i+1));j<=sb;j=(j+(2*i)+1)) {
                    s[j]=true;
                }
            }
        }
        sum =2;
        for (int i=1;i<=sb;i++){
            if(!s[i]) {
                sum=sum+(2*i+1);
            }
        }
        System.out.println(sum);
    }

    public static void main(String[] args) {
        long start = 0, end=0;
        Problem10 p = new Problem10();
        start =(Calendar.getInstance()).getTimeInMillis();
        p.primesPE();
        end =(Calendar.getInstance()).getTimeInMillis();
        System.out.println(start + " - " + end  + " - " +(end-start));    

        start =(Calendar.getInstance()).getTimeInMillis();
        p.primesPE1();
        end =(Calendar.getInstance()).getTimeInMillis();
        System.out.println(start + " - " + end  + " - " +(end-start));

        start =(Calendar.getInstance()).getTimeInMillis();
        p.primesPE2();
        end =(Calendar.getInstance()).getTimeInMillis();
        System.out.println(start + " - " + end  + " - " +(end-start));

    }
}
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: