//package Eratosthenes5;
import java.io.IOException;
import java.io.*;
import java.util.*;
//import java.lang.Math.*;
//import java.text.DecimalFormat;
//import java.awt.*;
//import javax.swing.*;
public class Eratosthenes5 {
// This uses a BitSet instead of a boolean array to see
// if this saves any memory. It enables me to test approx.
// 8x as many numbers. 109905151 is no longer my max.
// The highest number I've reached, so far, is around 879,400,000.
//
// After giving more memory to the app, I can check for primes up
// to around 2 billion. I've not determined the upper limit, but
// I suspect it is the java max integer size. It finds almost
// 100 million primes in under a minute.
// 2^31 = 2,147,483,648
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException
{
int maxSize = 1;
int maxNumber;
int maxSearch;
int primeCount;
int maxPrime;
String name;
name = getTheMaxNumber();
while (name.compareTo("1") != 0)
{
long startTime = System.currentTimeMillis();
maxSize = Integer.parseInt(name);
maxNumber = maxSize + 1;
maxSearch = (int) java.lang.Math.sqrt(maxNumber);
primeCount = 1; //Start the count at 1 because 2 is prime and we'll start at 3
maxPrime = -1;
//use a BitSet array to maximize how many primes can be found
BitSet numbList = new BitSet( maxNumber );
numbList.set(0, maxNumber-1, true); //set all bits to true
numbList.clear(0);
numbList.clear(1);
//clear the even numbers (except 2, it's prime)
for (long k = 4; k <= maxSize; k+=2)
{
numbList.clear((int)k);
}
// sieve out the non-primes
for (int k = 3; k < maxSearch; k+=2)
{
if (numbList.get(k))
{
sieveTheRest(k, numbList, maxSize);
}
}
//Count the primes
for (int k = 3; k <= maxSize; k+=2)
{
if (numbList.get(k))
{
maxPrime = k;
primeCount +=1;
if (primeCount % 1000000 == 0)
{
System.out.format("the " + ((primeCount/1000000 < 100) ? " " : "")
+ ((primeCount/1000000 < 10) ? " " : "")
+ primeCount/1000000 + " millionth prime is: %,11d%n",maxPrime);
}
}
}
//we're done
System.out.format("\nMy integer from beg: %,11d%n", Integer.parseInt(name));
System.out.format("array size : %,11d%n", maxNumber);
// System.out.format("prime count : %,11d%n", primeCount);
System.out.format("prime count : %,11d%n", numbList.cardinality());
System.out.format("largest prime found: %,11d%n", maxPrime);
System.out.format("max factor : %,11d%n \n", maxSearch);
long stopTime = System.currentTimeMillis();
System.out.println("That took " + (stopTime - startTime)/1000.0 + " seconds");
name = getTheMaxNumber();
}//end of while
System.out.println("\nEnd of program");
}//End of method Main
/**
*
* @return Passes back a string holding the maximum number to check
*/
static String getTheMaxNumber()
{
BufferedReader dataIn = new BufferedReader(new
InputStreamReader( System.in) );
String bigNumber = "";
System.out.print("Please enter an integer value (1 to quit): ");
try
{
bigNumber = dataIn.readLine();
}
catch( IOException e )
{
System.out.println("Error!");
}
return bigNumber;
}
/**
* @param myPrime The latest prime to be found.
* @param theBitSet The BitSet holding the prime flags
* @param maxSize The largest index in the BitSet
*/
static void sieveTheRest(int myPrime, BitSet theBitSet, int maxSize)
{
for (long k = myPrime*myPrime; k <= maxSize; k+=2*myPrime)
{
theBitSet.clear((int) k);
}
}
}//End of Class eratosthenes5
//package Eratosthenes5;
import java.io.IOException;
import java.io.*;
import java.util.*;
//import java.lang.Math.*;
//import java.text.DecimalFormat;
//import java.awt.*;
//import javax.swing.*;
public class Eratosthenes5 {
// This uses a BitSet instead of a boolean array to see
// if this saves any memory. It enables me to test approx.
// 8x as many numbers. 109905151 is no longer my max.
// The highest number I've reached, so far, is around 879,400,000.
//
// After giving more memory to the app, I can check for primes up
// to around 2 billion. I've not determined the upper limit, but
// I suspect it is the java max integer size. It finds almost
// 100 million primes in under a minute.
// 2^31 = 2,147,483,648
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException
{
int maxSize = 1;
int maxNumber;
int maxSearch;
int primeCount;
int maxPrime;
String name;
name = getTheMaxNumber();
while (name.compareTo("1") != 0)
{
maxSize = Integer.parseInt(name);
maxNumber = maxSize + 1;
maxSearch = (int) java.lang.Math.sqrt(maxNumber);
primeCount = 1; //Start the count at 1 because 2 is prime and we'll start at 3
maxPrime = -1;
//use a BitSet array to maximize how many primes can be found
BitSet numbList = new BitSet( maxNumber );
numbList.set(0, maxNumber-1, true); //set all bits to true
numbList.clear(0);
numbList.clear(1);
//clear the even numbers (except 2, it's prime)
for (long k = 4; k <= maxSize; k+=2)
{
numbList.clear((int)k);
}
// sieve out the non-primes
for (int k = 3; k < maxSearch; k+=2)
{
if (numbList.get(k))
{
sieveTheRest(k, numbList, maxSize);
}
}
//Count the primes
for (int k = 3; k <= maxSize; k+=2)
{
if (numbList.get(k))
{
maxPrime = k;
primeCount +=1;
if (primeCount % 1000000 == 0)
{
System.out.format("the " + ((primeCount/1000000 < 100) ? " " : "")
+ ((primeCount/1000000 < 10) ? " " : "")
+ primeCount/1000000 + " millionth prime is: %,11d%n",maxPrime);
}
}
}
//we're done
System.out.format("\nMy integer from beg: %,11d%n", Integer.parseInt(name));
System.out.format("array size : %,11d%n", maxNumber);
// System.out.format("prime count : %,11d%n", primeCount);
System.out.format("prime count : %,11d%n", numbList.cardinality());
System.out.format("largest prime found: %,11d%n", maxPrime);
System.out.format("max factor : %,11d%n \n", maxSearch);
name = getTheMaxNumber();
}//end of while
System.out.println("\nEnd of program");
}//End of method Main
/**
*
* @return Passes back a string holding the maximum number to check
*/
static String getTheMaxNumber()
{
BufferedReader dataIn = new BufferedReader(new
InputStreamReader( System.in) );
String bigNumber = "";
System.out.print("Please enter an integer value: ");
try
{
bigNumber = dataIn.readLine();
}
catch( IOException e )
{
System.out.println("Error!");
}
return bigNumber;
}
/**
* @param myPrime The latest prime to be found.
* @param theBitSet The BitSet holding the prime flags
* @param maxSize The largest index in the BitSet
*/
static void sieveTheRest(int myPrime, BitSet theBitSet, int maxSize)
{
for (long k = myPrime*myPrime; k <= maxSize; k+=2*myPrime)
{
theBitSet.clear((int) k);
}
}
}//End of Class eratosthenes5
//package Eratosthenes5;
import java.io.IOException;
import java.io.*;
import java.util.*;
//import java.lang.Math.*;
//import java.text.DecimalFormat;
//import java.awt.*;
//import javax.swing.*;
public class Eratosthenes5 {
// This uses a BitSet instead of a boolean array to see
// if this saves any memory. It enables me to test approx.
// 8x as many numbers. 109905151 is no longer my max.
// The highest number I've reached, so far, is around 879,400,000.
//
// After giving more memory to the app, I can check for primes up
// to around 2 billion. I've not determined the upper limit, but
// I suspect it is the java max integer size. It finds almost
// 100 million primes in under a minute.
// 2^31 = 2,147,483,648
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException
{
int maxSize = 1;
int maxNumber;
int maxSearch;
int primeCount;
int maxPrime;
String name;
name = getTheMaxNumber();
while (name.compareTo("1") != 0)
{
long startTime = System.currentTimeMillis();
maxSize = Integer.parseInt(name);
maxNumber = maxSize + 1;
maxSearch = (int) java.lang.Math.sqrt(maxNumber);
primeCount = 1; //Start the count at 1 because 2 is prime and we'll start at 3
maxPrime = -1;
//use a BitSet array to maximize how many primes can be found
BitSet numbList = new BitSet( maxNumber );
numbList.set(0, maxNumber-1, true); //set all bits to true
numbList.clear(0);
numbList.clear(1);
//clear the even numbers (except 2, it's prime)
for (long k = 4; k <= maxSize; k+=2)
{
numbList.clear((int)k);
}
// sieve out the non-primes
for (int k = 3; k < maxSearch; k+=2)
{
if (numbList.get(k))
{
sieveTheRest(k, numbList, maxSize);
}
}
//Count the primes
for (int k = 3; k <= maxSize; k+=2)
{
if (numbList.get(k))
{
maxPrime = k;
primeCount +=1;
if (primeCount % 1000000 == 0)
{
System.out.format("the " + ((primeCount/1000000 < 100) ? " " : "")
+ ((primeCount/1000000 < 10) ? " " : "")
+ primeCount/1000000 + " millionth prime is: %,11d%n",maxPrime);
}
}
}
//we're done
System.out.format("\nMy integer from beg: %,11d%n", Integer.parseInt(name));
System.out.format("array size : %,11d%n", maxNumber);
// System.out.format("prime count : %,11d%n", primeCount);
System.out.format("prime count : %,11d%n", numbList.cardinality());
System.out.format("largest prime found: %,11d%n", maxPrime);
System.out.format("max factor : %,11d%n \n", maxSearch);
long stopTime = System.currentTimeMillis();
System.out.println("That took " + (stopTime - startTime)/1000.0 + " seconds");
name = getTheMaxNumber();
}//end of while
System.out.println("\nEnd of program");
}//End of method Main
/**
*
* @return Passes back a string holding the maximum number to check
*/
static String getTheMaxNumber()
{
BufferedReader dataIn = new BufferedReader(new
InputStreamReader( System.in) );
String bigNumber = "";
System.out.print("Please enter an integer value (1 to quit): ");
try
{
bigNumber = dataIn.readLine();
}
catch( IOException e )
{
System.out.println("Error!");
}
return bigNumber;
}
/**
* @param myPrime The latest prime to be found.
* @param theBitSet The BitSet holding the prime flags
* @param maxSize The largest index in the BitSet
*/
static void sieveTheRest(int myPrime, BitSet theBitSet, int maxSize)
{
for (long k = myPrime*myPrime; k <= maxSize; k+=2*myPrime)
{
theBitSet.clear((int) k);
}
}
}//End of Class eratosthenes5
Using a BitSetBitSet to hold the numbers is pretty efficient. I've been able to find the primes up to about 2 billion using one. This finds almost 100 million primes in well under a minute.
Using Sieve of Eratosthenes logic, you don't have to do ANY dividing. It just isn't required. I also used a BitSetBitSet to maximize how many numbers I could check.
Here's my implementation:
//package Eratosthenes5;
import java.io.IOException;
import java.io.*;
import java.util.*;
//import java.lang.Math.*;
//import java.text.DecimalFormat;
//import java.awt.*;
//import javax.swing.*;
public class Eratosthenes5 {
// This uses a BitSet instead of a boolean array to see
// if this saves any memory. It enables me to test approx.
// 8x as many numbers. 109905151 is no longer my max.
// The highest number I've reached, so far, is around 879,400,000.
//
// After giving more memory to the app, I can check for primes up
// to around 2 billion. I've not determined the upper limit, but
// I suspect it is the java max integer size. It finds almost
// 100 million primes in under a minute.
// 2^31 = 2,147,483,648
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException
{
int maxSize = 1;
int maxNumber;
int maxSearch;
int primeCount;
int maxPrime;
String name;
name = getTheMaxNumber();
while (name.compareTo("1") != 0)
{
maxSize = Integer.parseInt(name);
maxNumber = maxSize + 1;
maxSearch = (int) java.lang.Math.sqrt(maxNumber);
primeCount = 1; //Start the count at 1 because 2 is prime and we'll start at 3
maxPrime = -1;
//use a BitSet array to maximize how many primes can be found
BitSet numbList = new BitSet( maxNumber );
numbList.set(0, maxNumber-1, true); //set all bits to true
numbList.clear(0);
numbList.clear(1);
//clear the even numbers (except 2, it's prime)
for (long k = 4; k <= maxSize; k+=2)
{
numbList.clear((int)k);
}
// sieve out the non-primes
for (int k = 3; k < maxSearch; k+=2)
{
if (numbList.get(k))
{
sieveTheRest(k, numbList, maxSize);
}
}
//Count the primes
for (int k = 3; k <= maxSize; k+=2)
{
if (numbList.get(k))
{
maxPrime = k;
primeCount +=1;
if (primeCount % 1000000 == 0)
{
System.out.format("the " + ((primeCount/1000000 < 100) ? " " : "")
+ ((primeCount/1000000 < 10) ? " " : "")
+ primeCount/1000000 + " millionth prime is: %,11d%n",maxPrime);
}
}
}
//we're done
System.out.format("\nMy integer from beg: %,11d%n", Integer.parseInt(name));
System.out.format("array size : %,11d%n", maxNumber);
// System.out.format("prime count : %,11d%n", primeCount);
System.out.format("prime count : %,11d%n", numbList.cardinality());
System.out.format("largest prime found: %,11d%n", maxPrime);
System.out.format("max factor : %,11d%n \n", maxSearch);
name = getTheMaxNumber();
}//end of while
System.out.println("\nEnd of program");
}//End of method Main
/**
*
* @return Passes back a string holding the maximum number to check
*/
static String getTheMaxNumber()
{
BufferedReader dataIn = new BufferedReader(new
InputStreamReader( System.in) );
String bigNumber = "";
System.out.print("Please enter an integer value: ");
try
{
bigNumber = dataIn.readLine();
}
catch( IOException e )
{
System.out.println("Error!");
}
return bigNumber;
}
/**
* @param myPrime The latest prime to be found.
* @param theBitSet The BitSet holding the prime flags
* @param maxSize The largest index in the BitSet
*/
static void sieveTheRest(int myPrime, BitSet theBitSet, int maxSize)
{
for (long k = myPrime*myPrime; k <= maxSize; k+=2*myPrime)
{
theBitSet.clear((int) k);
}
}
}//End of Class eratosthenes5
Using a BitSet to hold the numbers is pretty efficient. I've been able to find the primes up to about 2 billion using one. This finds almost 100 million primes in well under a minute.
Using Sieve of Eratosthenes logic, you don't have to do ANY dividing. It just isn't required. I also used a BitSet to maximize how many numbers I could check.
Using a BitSet to hold the numbers is pretty efficient. I've been able to find the primes up to about 2 billion using one. This finds almost 100 million primes in well under a minute.
Using Sieve of Eratosthenes logic, you don't have to do ANY dividing. It just isn't required. I also used a BitSet to maximize how many numbers I could check.
Here's my implementation:
//package Eratosthenes5;
import java.io.IOException;
import java.io.*;
import java.util.*;
//import java.lang.Math.*;
//import java.text.DecimalFormat;
//import java.awt.*;
//import javax.swing.*;
public class Eratosthenes5 {
// This uses a BitSet instead of a boolean array to see
// if this saves any memory. It enables me to test approx.
// 8x as many numbers. 109905151 is no longer my max.
// The highest number I've reached, so far, is around 879,400,000.
//
// After giving more memory to the app, I can check for primes up
// to around 2 billion. I've not determined the upper limit, but
// I suspect it is the java max integer size. It finds almost
// 100 million primes in under a minute.
// 2^31 = 2,147,483,648
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException
{
int maxSize = 1;
int maxNumber;
int maxSearch;
int primeCount;
int maxPrime;
String name;
name = getTheMaxNumber();
while (name.compareTo("1") != 0)
{
maxSize = Integer.parseInt(name);
maxNumber = maxSize + 1;
maxSearch = (int) java.lang.Math.sqrt(maxNumber);
primeCount = 1; //Start the count at 1 because 2 is prime and we'll start at 3
maxPrime = -1;
//use a BitSet array to maximize how many primes can be found
BitSet numbList = new BitSet( maxNumber );
numbList.set(0, maxNumber-1, true); //set all bits to true
numbList.clear(0);
numbList.clear(1);
//clear the even numbers (except 2, it's prime)
for (long k = 4; k <= maxSize; k+=2)
{
numbList.clear((int)k);
}
// sieve out the non-primes
for (int k = 3; k < maxSearch; k+=2)
{
if (numbList.get(k))
{
sieveTheRest(k, numbList, maxSize);
}
}
//Count the primes
for (int k = 3; k <= maxSize; k+=2)
{
if (numbList.get(k))
{
maxPrime = k;
primeCount +=1;
if (primeCount % 1000000 == 0)
{
System.out.format("the " + ((primeCount/1000000 < 100) ? " " : "")
+ ((primeCount/1000000 < 10) ? " " : "")
+ primeCount/1000000 + " millionth prime is: %,11d%n",maxPrime);
}
}
}
//we're done
System.out.format("\nMy integer from beg: %,11d%n", Integer.parseInt(name));
System.out.format("array size : %,11d%n", maxNumber);
// System.out.format("prime count : %,11d%n", primeCount);
System.out.format("prime count : %,11d%n", numbList.cardinality());
System.out.format("largest prime found: %,11d%n", maxPrime);
System.out.format("max factor : %,11d%n \n", maxSearch);
name = getTheMaxNumber();
}//end of while
System.out.println("\nEnd of program");
}//End of method Main
/**
*
* @return Passes back a string holding the maximum number to check
*/
static String getTheMaxNumber()
{
BufferedReader dataIn = new BufferedReader(new
InputStreamReader( System.in) );
String bigNumber = "";
System.out.print("Please enter an integer value: ");
try
{
bigNumber = dataIn.readLine();
}
catch( IOException e )
{
System.out.println("Error!");
}
return bigNumber;
}
/**
* @param myPrime The latest prime to be found.
* @param theBitSet The BitSet holding the prime flags
* @param maxSize The largest index in the BitSet
*/
static void sieveTheRest(int myPrime, BitSet theBitSet, int maxSize)
{
for (long k = myPrime*myPrime; k <= maxSize; k+=2*myPrime)
{
theBitSet.clear((int) k);
}
}
}//End of Class eratosthenes5
Using a BitSet to hold the numbers is pretty efficient. I've been able to find the primes up to about 2 billion using one. This finds almost 100 million primes in well under a minute.
I can post the code if there is any interest, but I make NO claims for its quality. I also don't claim to be a good object-oriented programmer.
Using Sieve of Eratosthenes logic, you don't have to do ANY dividing. It just isn't required. I also used a BitSet to maximize how many numbers I could check.
I found that I needed a separate loop to 'sieve' out the even numbers higher than 2. The main logic just didn't work for 2.
Also, when marking out the non-primes, you only need to start at the square of the prime you just found. This is because any smaller non-prime will have already been 'sieved' out because it is divisible by a smaller prime, which you will have already found and processed. Also, your increment for the 'sieve' can be 2 times the prime you're sieving for (because the others would be even numbers, so no need to check them).
lang-java