Re: Sum of Primes < 1000000
Hi Luc,
I found the primes<1000000 and stored them in an array.also summed them
up.I am pasting my code.Pls hav a look..........it took 1782 msecs on a
p4 2.4GHz processor && 512 mb ram.
If this code is not ok then let me know:)
/*
* Created on Jan 7, 2007
*
* To change the template for this generated file go to
* Window>Preferences>Java>Code Generation>Code and
Comments
*/
package src;
//import java.lang.Math;
/**
* @author Jboss
*calculate sum of prime nos less than 1 million
*/
public final class Sum_Prime {
private static int currNo;
private static int currSqrt;
private static int[] primeArr;
private static long currSum = 0;
private static final int range = 1000000; // calc till 1000000;
private static long startTime;
public static void main(String[] args) {
//Math.sqrt()
int currArrSize = range / 20;//holds the curr size of the array
if (currArrSize == 0)
{
primeArr = new int[10];
currArrSize=10;
}
else
primeArr = new int[currArrSize];
startTime = System.currentTimeMillis();
int k = 0; //index of the array which stores the prime nos.
currNo = 2; //start looking from 2
System.out.print("\n arr size \t"+primeArr.length);
for (int i = 2; i <= range; i++) {
boolean isPrime = true;
currSqrt = (int) Math.sqrt(currNo);
for (int j = 2;
j <= currSqrt;
j++) //chk for 3 whose sqrt is 1.5....
{
if (currNo % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
try {
primeArr[k] = currNo;
currSum = currSum + currNo;
k++;
} catch (ArrayIndexOutOfBoundsException arrex) {
currArrSize=currArrSize*2;
int[] tempArr = new int[currArrSize];
System.arraycopy(primeArr, 0, tempArr, 0,k);//copies the old arr
into new 1
primeArr=tempArr;
//System.out.print("\n primeArr size \t"+primeArr.length);
//System.out.print("\n tempArr size \t"+tempArr.length);
primeArr[k]=currNo;
currSum = currSum + currNo;
System.out.print("\n new arr size \t"+primeArr.length);
k++;
}
}
currNo++;
}
System.out.print("\n sum \t" + currSum);
System.out.print("\n curr val \t" + currNo);
System.out.print("\n nos found \t" + k);
System.out.print(
"\n Time taken to execute in millisecs \t"
+ (System.currentTimeMillis() - startTime));
System.exit(0);
}
}
tell me the name of the site. where u saw this..........
Luc The Perverse wrote:
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%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.
--
LTP
:)