# Sieve of Eratosthenes & Primality test

## Recommended Posts

Not super useful for scripting, but here you go.

```package org.bjornkrols.math;

import java.util.BitSet;

/**
* @author 		Bjorn Krols (Botre)
* @version		0.2
* @since		April 16, 2015
*/

public final class SieveOfEratosthenes {

public static void main(String[] args) {
SieveOfEratosthenes sieve = new SieveOfEratosthenes(100);
System.out.println(sieve.isPrime(29));
}

public BitSet sieve;

public SieveOfEratosthenes(int n) {
calculate(n);
}

private void calculate(int n) {
sieve = new BitSet(n);
// Assume all numbers are prime.
for (int i = 2; i < sieve.size(); i++) sieve.set(i, true);
// Find the square root of n.
double sqrtn = Math.floor(Math.sqrt(n));
for (int i = 2; i < sqrtn; i++) if (sieve.get(i)) for (int j = i * i; j < n; j += i) sieve.set(j, false);
}

public boolean isPrime(int n) {
return sieve.get(n);
}

}```
```package org.bjornkrols.math;

/**
* @author 		Bjorn Krols (Botre)
* @version		0.0
* @since		April 16, 2015
*/

public final class PrimalityTest {

private PrimalityTest() {
// This class should never be instantiated.
// Do not delete or make accessible.
}

public static boolean test(long n) {
// A whole number greater than one is called a prime number if its only positive divisors (factors) are one and itself.
// All whole numbers between 1 and 3 are prime.
if (n <= 3)  return n > 1;
// All multiples of 2 and 3 are not prime.
if (n % 2 == 0 || n % 3 == 0) return false;
// Find the square root of n.
double sqrtn = Math.floor(Math.sqrt(n));
// All primes are of the form 6k ± 1 (with the exception of 2 and 3).
for (int divisor = 5; divisor <= sqrtn; divisor += 6) if (n % divisor == 0 || n % (divisor + 2) == 0) return false;
return true;
}

}```
```2 true
3 true
5 true
7 true
11 true
13 true
17 true
19 true
23 true
29 true
31 true
37 true
41 true
43 true
47 true
53 true
59 true
61 true
67 true
71 true
73 true
79 true
83 true
89 true
97 true```
Edited by Botre
##### Share on other sites

Thats actually really interesting. Nice visuals

##### Share on other sites

Thats actually really interesting. Nice visuals

Visuals courtesy of Wikipedia :x

##### Share on other sites

Visuals courtesy of Wikipedia :x

WOW. Ive just lost all my respect for you...

##### Share on other sites

WOW. Ive just lost all my respect for you...

```package org.bjornkrols.fun;

import java.util.Random;

/**
* @author 		Bjorn Krols (Botre)
* @version		0.0
* @since		April 16, 2015
*/

public class Coin {

public static void main(String[] args) {
Coin coin = new Coin();
coin.toss();
}

private static final Random RANDOM = new Random();

public Coin() {
toss();
}

public void toss() {
}

}

public boolean isTails() {
}

}
```

I'm bored

Edited by Botre
##### Share on other sites

Not super useful for scripting, but here you go.

```/**
* @author 		Bjorn Krols (Botre)
* @version		0.1
* @since		April 16, 2015
*/

public final class SieveOfEratosthenes {

public static void main(String[] args) {
boolean[] set = calculate(100);
for (int i = 0; i < set.length; i++) if (set[i]) System.out.println(i + " " + PrimalityTest.test(i));
}

private SieveOfEratosthenes() {
// This class should never be instantiated.
// Do not delete or make accessible.
}

public static boolean[] calculate(int n) {
boolean[] isPrime = new boolean[n];
// Assume all numbers are prime.
for (int i = 2; i < isPrime.length; i++) isPrime[i] = true;
// Find the square root of n.
double sqrtn = Math.floor(Math.sqrt(n));
for (int i = 2; i < sqrtn; i++) if (isPrime[i]) for (int j = i * i; j < n; j += i) isPrime[j] = false;
return isPrime;
}

}```
```package org.bjornkrols.math;

/**
* @author 		Bjorn Krols (Botre)
* @version		0.0
* @since		April 16, 2015
*/

public final class PrimalityTest {

private PrimalityTest() {
// This class should never be instantiated.
// Do not delete or make accessible.
}

public static boolean test(long n) {
// A whole number greater than one is called a prime number if its only positive divisors (factors) are one and itself.
// All whole numbers between 1 and 3 are prime.
if (n <= 3)  return n > 1;
// All multiples of 2 and 3 are not prime.
if (n % 2 == 0 || n % 3 == 0) return false;
// Find the square root of n.
double sqrtn = Math.floor(Math.sqrt(n));
// All primes are of the form 6k ± 1 (with the exception of 2 and 3).
for (int divisor = 5; divisor <= sqrtn; divisor += 6) if (n % divisor == 0 || n % (divisor + 2) == 0) return false;
return true;
}

}```
```2 true
3 true
5 true
7 true
11 true
13 true
17 true
19 true
23 true
29 true
31 true
37 true
41 true
43 true
47 true
53 true
59 true
61 true
67 true
71 true
73 true
79 true
83 true
89 true
97 true```

We did this in my intro to OO programming class, what are you doing it in?

##### Share on other sites

We did this in my intro to OO programming class, what are you doing it in?

Gold ol' boredom :l

##### Share on other sites

If you're really bored create a parallel version

##### Share on other sites

```	public static boolean test(long n) {
if (n <= 3)  return n > 1;
if (n % 2 == 0 || n % 3 == 0) return false;
double sqrtn = Math.floor(Math.sqrt(n));
for (int divisor = 5; divisor <= sqrtn; divisor += 6) if (n % divisor == 0 || n % (divisor + 2) == 0) return false;
return true;
}```
```public static boolean isPrime(long n) { //from wikipedia
if (n <= 3) {
return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return false;
} else {
double sqrtN = Math.floor(Math.sqrt(n));
for (int i = 5; i <= sqrtN; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
}
```

looks like you just changed the brackets?

##### Share on other sites

```public static boolean isPrime(long n) { //from wikipedia
if (n <= 3) {
return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return false;
} else {
double sqrtN = Math.floor(Math.sqrt(n));
for (int i = 5; i <= sqrtN; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
}
```

looks like you just changed the brackets?

What else should I have changed?

##### Share on other sites

What else should I have changed?

Nothing you should've wrote yourself??????????

##### Share on other sites

Nothing you should've wrote yourself??????????

(bye bye)

Edited by Botre
##### Share on other sites

Use a BitSet instead of a bool array

##### Share on other sites

Use a BitSet instead of a bool array

Thanks, I just learned something :x !

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.