L
Luc The Perverse
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 -= 2;
if(p2 == 0)
Prime = false;
if(p2 < 1)
p2 += pc;
}
if(Prime){
pc[c] = cn;
p2[c++] = cn;
if((c%2048) == 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.
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 -= 2;
if(p2 == 0)
Prime = false;
if(p2 < 1)
p2 += pc;
}
if(Prime){
pc[c] = cn;
p2[c++] = cn;
if((c%2048) == 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.