I was messing around on a site where you answer questions for points. (No

prizes or anything)

Anyway, they say our programs *should* execute in less than 1 minute if well

formed.

Mine didn't - it was less than 10 minutes though and I got the right answer.

I was supposed to sum all primes less than 1 million.

Is there an algorithm out there, which I will be able to understand, which

works significantly faster than this one?

//import java.lang.*;

import java.util.*;

import java.math.*;

public class prob10{

public static void main(String[] x){

if(x.length<1){

System.out.println("enter a number");

return;

}

int n = Integer.parseInt(x[0]);

int c = 0;

int[] pc = new int[n];

int[] p2 = new int[n];

if(n<=1){

System.out.println(2);

return;

}

c++;

pc[0] = 2;

p2[0] = 2;

int cn = 1;

long g = 2;

while(c<n){

cn+=2;

boolean Prime = true;

for(int i=1;i<c;i++){

p2[i] -= 2;

if(p2[i] == 0)

Prime = false;

if(p2[i] < 1)

p2[i] += pc[i];

}

if(Prime){

pc[c] = cn;

p2[c++] = cn;

if((c%204

== 0)

System.out.println(cn);

if(cn<1000000)

g+=cn;

else{

System.out.println("Yay 1 million reached!");

break;

}

}

}

System.out.println("Grand Total " + g);

System.out.println(pc[n-1]);

}

}

I specifically tried to avoid ever dividing or modding (except in my status

reporter, but that only checks when a prime has been found)

I "count down" until the next multiple a prime is detected.

The algorithm works . . but it is n^2 complexity, and kinda sucks.

--

LTP