fastest time?

N

Neil Morris

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++;
}
}
}
}
 
R

Roedy Green

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
 
D

Daniel Pitts

Neil said:
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)");
}
}
 
N

Neil Morris

Daniel said:
Neil said:
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)");
}
}
 
R

Roger Lindsjö

Daniel said:
Neil said:
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.
 
A

Arne Vajhøj

Neil said:
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);
}
}
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top