import java.io.PrintStream; /** * sieve of Eratosthenes using a primitive bit array using bit-shift and bit-and *
* ported from http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm * * Created by Xan Gregg. * Date: Nov 13, 2004 */ public class FindPrimes7 { public static void main(String[] args) { long start = System.currentTimeMillis(); //long count = findPrimes(10000, System.out); long count = findPrimes(10000000, new PrintStream(new NullOutputStream())); long end = System.currentTimeMillis(); long elapsed = end - start; System.out.println("Primes: " + count + "; seconds: " + elapsed / 1000.0); } private static int[] createBitArray(long bits) { return new int[(int) (bits >> 5) + 1]; } private static void setBit(int ba[], long bitSS) { ba[(int) (bitSS >> 5)] |= 1 << (bitSS & 31); } private static void clearBit(int ba[], long bitSS) { ba[(int) (bitSS >> 5)] &= ~(1 << (bitSS & 31)); } private static boolean getBit(int ba[], long bitSS) { int cell = ba[(int) (bitSS >> 5)]; return (cell & (1 << (bitSS & 31))) != 0; } private static void clearAll(int ba[]) { for (int ss = 0; ss < ba.length; ss++) ba[ss] = 0; } private static void setAll(int ba[]) { for (int ss = 0; ss < ba.length; ss++) ba[ss] = -1; } public static long findPrimes(long topCandidate, PrintStream out) { long count = 0; int[] ba = createBitArray(topCandidate); /* SET ALL BUT 0 AND 1 TO PRIME STATUS */ setAll(ba); clearBit(ba, 0); clearBit(ba, 1); /* MARK ALL THE NON-PRIMES */ long thisFactor = 2; long lastSquare = 0; long thisSquare; while (thisFactor * thisFactor <= topCandidate) { /* MARK THE MULTIPLES OF THIS FACTOR */ long mark = thisFactor + thisFactor; while (mark <= topCandidate) { clearBit(ba, mark); mark += thisFactor; } /* PRINT THE PROVEN PRIMES SO FAR */ thisSquare = thisFactor * thisFactor; for (; lastSquare < thisSquare; lastSquare++) { if (getBit(ba, lastSquare)) { out.println(lastSquare); count ++; } } /* SET thisFactor TO NEXT PRIME */ thisFactor++; while (!getBit(ba, thisFactor)) thisFactor++; } /* PRINT THE REMAINING PRIMES */ for (; lastSquare <= topCandidate; lastSquare++) { if (getBit(ba, lastSquare)) { out.println(lastSquare); count ++; } } return count; } }