«

Dear All
I rang the following code for finding prime numbers the results I got
for my computer is
105097565 prime numbers
2147483629 being the highest
13:31:14 taken 13 hours 31 minutes and 14 seconds

can anyone beat this on a computer, also how does this compare to a
mainframe/server farm setup

Thanks in advance
Neil Morris
ps I am using intek QX9650 4gb ram



import java.lang.*;

public class prime {

public static void main(String[] args) {
double start=(double)System.currentTimeMillis();
int input=Integer.MAX_VALUE;
int count=1;
for(int number=1;number<input;number++) {
boolean prime=true;
for(int i=2;(i*i>0)&&(i*i<=number);i++) {
if (number%i==0) {
prime=false;
break;
}
}
if(prime) {
double next=(double)System.currentTimeMillis();
double diff=(next-start)/1000;
double days=Math.floor(diff/86400);
diff=diff-(days*86400);
double hours=Math.floor(diff/3600);
diff=diff-(hours*3600);
double minutes=Math.floor(diff/60);
double seconds=diff-(minutes*60);
System.out.println(count+") "+number+"
:"+(long)days+":"+(long)hours+":"+(long)minutes+": "+(long)seconds+":");
count++;
}
}
}
}

On Sun, 15 Jun 2008 16:55:00 +0100, Neil Morris
<> wrote, quoted or indirectly quoted someone
who said :

> public static void main(String[] args) {
> double start=(double)System.currentTimeMillis();
> int input=Integer.MAX_VALUE;
> int count=1;
> for(int number=1;number<input;number++) {
> boolean prime=true;
> for(int i=2;(i*i>0)&&(i*i<=number);i++) {
> if (number%i==0) {
> prime=false;
> break;
> }
> }

There are many faster algorithms than that. You don't need to divide
by anything unless it is prime.

You can use a seive.

See http://mindprod.com/jgloss/prime.html
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Neil Morris wrote:
> Dear All
> I rang the following code for finding prime numbers the results I got
> for my computer is
> 105097565 prime numbers
> 2147483629 being the highest
> 13:31:14 taken 13 hours 31 minutes and 14 seconds
>
> can anyone beat this on a computer, also how does this compare to a
> mainframe/server farm setup
>
> Thanks in advance
> Neil Morris
> ps I am using intek QX9650 4gb ram
>
[snip op code]
On my machine: the following got the same results as you, in 5 minutes.
It is a bit more memory intensive, you'll have to run it with "java
-Xmx786M PrimeSeive" to avoid OutOfMemoryException.

import java.util.BitSet;

public class PrimeSeive {
public static void main(String[] args) {
final long startTime = System.currentTimeMillis();
long lastUpdate = startTime;
final BitSet composites = new BitSet(Integer.MAX_VALUE);
composites.set(0);
composites.set(1);
for (int j = 4; j >= 0 && j < Integer.MAX_VALUE; j += 2) {
composites.set(j);
}
int primes = 2;
int highestPrime = 2;
for (int prime = 1; prime < Integer.MAX_VALUE; ) {
prime = composites.nextClearBit(prime+2);
if (prime == Integer.MAX_VALUE) {
break;
}
primes++;
highestPrime = prime;
if (System.currentTimeMillis() - lastUpdate > 200) {
lastUpdate = System.currentTimeMillis();
printUpdate(startTime, primes, prime);
}
for (int j = prime * 2;
j >= 0 && j < Integer.MAX_VALUE;
j += prime) {
composites.set(j);
}
}
printUpdate(startTime, primes, highestPrime);
}

static void printUpdate(long startTime, int primes, int prime) {
long timeDifference = System.currentTimeMillis() - startTime;
long seconds = (timeDifference /= 1000) % 60;
long minutes = (timeDifference /= 60) % 60;
long hours = (timeDifference /= 60) % 24;
long days = (timeDifference /= 24) % 7;
System.out.println(primes + ": ("+prime+") "+
days+" day(s), "+
hours+" hour(s) "+
minutes+" minute(s) and "+
seconds+" second(s)");
}
}
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

Daniel Pitts wrote:
> Neil Morris wrote:
>> Dear All
>> I rang the following code for finding prime numbers the results I got
>> for my computer is
>> 105097565 prime numbers
>> 2147483629 being the highest
>> 13:31:14 taken 13 hours 31 minutes and 14 seconds
>>
>> can anyone beat this on a computer, also how does this compare to a
>> mainframe/server farm setup
>>
>> Thanks in advance
>> Neil Morris
>> ps I am using intek QX9650 4gb ram
>>
> [snip op code]
> On my machine: the following got the same results as you, in 5 minutes.
> It is a bit more memory intensive, you'll have to run it with "java
> -Xmx786M PrimeSeive" to avoid OutOfMemoryException.
>
> import java.util.BitSet;
>
> public class PrimeSeive {
> public static void main(String[] args) {
> final long startTime = System.currentTimeMillis();
> long lastUpdate = startTime;
> final BitSet composites = new BitSet(Integer.MAX_VALUE);
> composites.set(0);
> composites.set(1);
> for (int j = 4; j >= 0 && j < Integer.MAX_VALUE; j += 2) {
> composites.set(j);
> }
> int primes = 2;
> int highestPrime = 2;
> for (int prime = 1; prime < Integer.MAX_VALUE; ) {
> prime = composites.nextClearBit(prime+2);
> if (prime == Integer.MAX_VALUE) {
> break;
> }
> primes++;
> highestPrime = prime;
> if (System.currentTimeMillis() - lastUpdate > 200) {
> lastUpdate = System.currentTimeMillis();
> printUpdate(startTime, primes, prime);
> }
> for (int j = prime * 2;
> j >= 0 && j < Integer.MAX_VALUE;
> j += prime) {
> composites.set(j);
> }
> }
> printUpdate(startTime, primes, highestPrime);
> }
>
> static void printUpdate(long startTime, int primes, int prime) {
> long timeDifference = System.currentTimeMillis() - startTime;
> long seconds = (timeDifference /= 1000) % 60;
> long minutes = (timeDifference /= 60) % 60;
> long hours = (timeDifference /= 60) % 24;
> long days = (timeDifference /= 24) % 7;
> System.out.println(primes + ": ("+prime+") "+
> days+" day(s), "+
> hours+" hour(s) "+
> minutes+" minute(s) and "+
> seconds+" second(s)");
> }
> }

Dear Daniel
Indeed your method is alot faster than my method, I guess the repeated
computions vs setting or unsetting bits in the BitSet data type goes to
show that if you have enough memory virtual or otherwise this is the
method to use!

ps the results from my machine is 2 minutes 55 seconds anyone can beat that?

Neil Morris

I used a edited version as follows it only shows the overall time


import java.util.BitSet;

public class PrimeSeive {
public static void main(String[] args) {
final long startTime = System.currentTimeMillis();
final BitSet composites = new BitSet(Integer.MAX_VALUE);
composites.set(0);
composites.set(1);
for (int j = 4; j >= 0 && j < Integer.MAX_VALUE; j += 2) {
composites.set(j);
}
int primes = 2;
int highestPrime = 2;
for (int prime = 1; prime < Integer.MAX_VALUE; ) {
prime = composites.nextClearBit(prime+2);
if (prime == Integer.MAX_VALUE) {
break;
}
primes++;
highestPrime = prime;
for (int j = prime * 2;
j >= 0 && j < Integer.MAX_VALUE;
j += prime) {
composites.set(j);
}
}
printUpdate(startTime, primes, highestPrime);
}

static void printUpdate(long startTime, int primes, int prime) {
long timeDifference = System.currentTimeMillis() - startTime;
long seconds = (timeDifference /= 1000) % 60;
long minutes = (timeDifference /= 60) % 60;
long hours = (timeDifference /= 60) % 24;
long days = (timeDifference /= 24) % 7;
System.out.println(primes + ": ("+prime+") "+
days+" day(s), "+
hours+" hour(s) "+
minutes+" minute(s) and "+
seconds+" second(s)");
}
}

Daniel Pitts wrote:
> Neil Morris wrote:
>> Dear All
>> I rang the following code for finding prime numbers the results I got
>> for my computer is
>> 105097565 prime numbers
>> 2147483629 being the highest
>> 13:31:14 taken 13 hours 31 minutes and 14 seconds
>>
>> can anyone beat this on a computer, also how does this compare to a
>> mainframe/server farm setup
>>
>> Thanks in advance
>> Neil Morris
>> ps I am using intek QX9650 4gb ram
>>
> [snip op code]
> On my machine: the following got the same results as you, in 5 minutes.
> It is a bit more memory intensive, you'll have to run it with "java
> -Xmx786M PrimeSeive" to avoid OutOfMemoryException.

On mine it takes just over 4 minutes. Then, if I just transform the
bitset to not include even numbers (thus halving the size), the time is
reduced to 2 min 40 seconds.

I'm sure there are even better algorithms, but I'm not sure what the
O.P. wanted to accomplish.

> import java.util.BitSet;
>
> public class PrimeSeive {
> public static void main(String[] args) {
> final long startTime = System.currentTimeMillis();
> long lastUpdate = startTime;
> final BitSet composites = new BitSet(Integer.MAX_VALUE);
> composites.set(0);
> composites.set(1);
> for (int j = 4; j >= 0 && j < Integer.MAX_VALUE; j += 2) {
> composites.set(j);
> }
> int primes = 2;
Why do you say you have 2 primes? I thought you only started with 1
prime (2).

> int highestPrime = 2;
> for (int prime = 1; prime < Integer.MAX_VALUE; ) {
> prime = composites.nextClearBit(prime+2);
> if (prime == Integer.MAX_VALUE) {
> break;
> }
> primes++;
> highestPrime = prime;
> if (System.currentTimeMillis() - lastUpdate > 200) {
> lastUpdate = System.currentTimeMillis();
> printUpdate(startTime, primes, prime);
> }
> for (int j = prime * 2;
> j >= 0 && j < Integer.MAX_VALUE;
> j += prime) {
start with prime * 3 and then step with prime * 2 since the other values
will be even which has already been set by your original "clear even" loop.

> composites.set(j);
> }
> }
> printUpdate(startTime, primes, highestPrime);
> }
>
> static void printUpdate(long startTime, int primes, int prime) {
> long timeDifference = System.currentTimeMillis() - startTime;
> long seconds = (timeDifference /= 1000) % 60;
> long minutes = (timeDifference /= 60) % 60;
> long hours = (timeDifference /= 60) % 24;
> long days = (timeDifference /= 24) % 7;
> System.out.println(primes + ": ("+prime+") "+
> days+" day(s), "+
> hours+" hour(s) "+
> minutes+" minute(s) and "+
> seconds+" second(s)");
> }
> }


--
Roger Lindsjö

Daniel Pitts wrote:
> public class PrimeSeive {

Maybe rename it to PrimeSieve ...



Arne

Neil Morris wrote:
> I rang the following code for finding prime numbers the results I got
> for my computer is
> 105097565 prime numbers
> 2147483629 being the highest
> 13:31:14 taken 13 hours 31 minutes and 14 seconds

This reminds me of the mid 1980's and playing with Macro-32.



See code below for one way of doing it.

Arne

================================================== ==

// run with -Xmx300m
public class Primes {
private final static int[] MASK = { 1, 2, 4, 8, 16, 32, 64, 128 };
private static boolean isBitSet(byte[] b, int ix) {
int bytix = ix >> 4;
int bitix = (ix & 0x0F) >> 1;
return (b[bytix] & MASK[bitix]) > 0;
}
private static void setBit(byte[] b, int ix) {
int bytix = ix >> 4;
int bitix = (ix & 0x0F) >> 1;
b[bytix] |= MASK[bitix];
}
private static void findPrimes(int n) {
long t1 = System.currentTimeMillis();
byte[] b = new byte[n / 16 + 1];
int sqrtn = (int)Math.sqrt(n);
for(int i = 3; i <= sqrtn; i += 2) {
if(!isBitSet(b, i)) {
for(int j = 3 * i; j <= n && j > 0; j += (2 * i)) {
setBit(b, j);
}
}
}
int nprim = 1;
for(int k = 3; k <= n && k > 0; k += 2) {
if(!isBitSet(b, k)) {
nprim++;
}
}
long t2 = System.currentTimeMillis();
System.out.println(nprim + " primes in " + n + " numbers -
found in " + (t2 - t1) / 1000.0 + " seconds");
}
public static void main(String[] args) {
findPrimes(100000);
// for reasons unknown to me it does not work with
Integer.MAX_VALUE if -server is used
findPrimes(Integer.MAX_VALUE - 1);
}
}