public boolean isPrime(int number) {
if (number == 1)
return false;
if (number == 2)
return true;
if (number % 2 == 0)
return false;
for (int d = 3; d <= (int) Math.sqrt(number); d++)
if (number % d == 0)
return false;
return true;
}
for (int d = 3; d <= (int)sqrt((double)number); d++)
However since we have already tested for even numbers, i.e. number % 2, we can safely increment the count to d + 2:
for (int d = 3; d <= (int)sqrt((double)number); d = d + 2)
Sieve of Eratostheneshttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them which is equal to that prime.
Simple Version:
http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
boolean[] isPrime = new boolean[N + 1]; // can be changed to use BitSet for space efficient
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
// mark non-primes <= N using Sieve of Eratosthenes
for (int i = 2; i*i <= N; i++) {
// if i is prime, then mark multiples of i as nonprime
// suffices to consider mutiples i, i+1, ..., N/i
if (isPrime[i]) {
for (int j = i; i*j <= N; j++) {
isPrime[i*j] = false;
}
}
}
// count primes
int primes = 0;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) primes++;
}
System.out.println("The number of primes <= " + N + " is " + primes);
}
位操作与空间压缩在上面程序是用bool数组来作标记的，bool型数据占1个字节（8位），因此用位操作来压缩下空间占用将会使空间的占用减少八分之七。
int flag[MAXN / 32 + 1];
int primes[MAXN / 3 + 1], pi;
void GetPrime_1()
{
int i, j;
pi = 0;
memset(flag, 0, sizeof(flag));
for (i = 2; i < MAXN; i++)
if (!((flag[i / 32] >> (i % 32)) & 1))
{
primes[pi++] = i;
for (j = i; j < MAXN; j += i)
flag[j / 32] |= (1 << (j % 32));
}
}
http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Prime_number_generationUse BitSet to save memory space.
public class Sieve
{
private BitSet sieve;
private Sieve() {}
private Sieve(int size) {
sieve = new BitSet((size+1)/2);
}
private boolean is_composite(int k)
{
assert k >= 3 && (k % 2) == 1;
return sieve.get((k-3)/2);
}
private void set_composite(int k)
{
assert k >= 3 && (k % 2) == 1;
sieve.set((k-3)/2);
}
public static List<Integer> sieve_of_eratosthenes(int max)
{
Sieve sieve = new Sieve(max + 1); // +1 to include max itself
for (int i = 3; i*i <= max; i += 2) {
if (sieve.is_composite(i))
continue;
// We increment by 2*i to skip even multiples of i
for (int multiple_i = i*i; multiple_i <= max; multiple_i += 2*i)
sieve.set_composite(multiple_i);
}
List<Integer> primes = new ArrayList<Integer>();
primes.add(2);
for (int i = 3; i <= max; i += 2)
if (!sieve.is_composite(i))
primes.add(i);
return primes;
}
}
Sieve of Atkin- Faster but hard to understand
http://en.wikipedia.org/wiki/Sieve_of_Atkin
the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes which does some preliminary work and then marks off multiples of the square of each prime, rather than multiples of the prime itself.
http://bcbutler.com/Java_Tuts/java_sieve_of_atkins.php
public class AtkinSieve {
public static int[] findPrimes(int arraySize) {
boolean[] isPrime = new boolean[arraySize + 1];
double sqrt = Math.sqrt(arraySize);
for (int x = 1; x <= sqrt; x++) {
for (int y = 1; y <= sqrt; y++) {
int n = 4 * x * x + y * y;
if (n <= arraySize && (n % 12 == 1 || n % 12 == 5)) {
isPrime[n] = !isPrime[n];
}
n = 3 * x * x + y * y;
if (n <= arraySize && (n % 12 == 7)) {
isPrime[n] = !isPrime[n];
}
n = 3 * x * x - y * y;
if (x > y && (n <= arraySize) && (n % 12 == 11)) {
isPrime[n] = !isPrime[n];
}
}
}
for (int n = 5; n <= sqrt; n++) {
if (isPrime[n]) {
int s = n * n;
for (int k = s; k <= arraySize; k += s) {
isPrime[k] = false;
}
}
}
int[] primes = new int[arraySize];
int found = 0;
if (arraySize > 2) {
primes[found++] = 2;
}
if (arraySize > 3) {
primes[found++] = 3;
}
for (int n = 5; n <= arraySize; n += 2) {
if (isPrime[n]) {
primes[found++] = n;
}
}
return Arrays.copyOf(primes, found);
}
}
