Sieve of Eratosthenes & Primality test

[Botre]

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 April 30, 2015 by Botre

[AresScripts]

Thats actually really interesting. Nice visuals

[Botre]

Thats actually really interesting. Nice visuals

 

Visuals courtesy of Wikipedia :x

[AresScripts]

Visuals courtesy of Wikipedia :x

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

[Botre]

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

 

Heads or tails?

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();
		if (coin.isHeads() || coin.isTails()) System.out.println(":doge:");
	}

	private static final Random RANDOM = new Random();

	private boolean heads;

	public Coin() {
		toss();
	}

	public void toss() {
		heads = RANDOM.nextBoolean();
	}

	public boolean isHeads() {
		return heads;
	}

	public boolean isTails() {
		return !heads;
	}

}

I'm bored

Edited April 16, 2015 by Botre

[Mysteryy]

 

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?

[Botre]

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

Gold ol' boredom :l

[Flamezzz]

If you're really bored create a parallel version 

[Japani]

	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?

[Botre]

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?

[Japani]

What else should I have changed?

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

[Botre]

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

 

 

(bye bye)

Edited April 16, 2015 by Botre

[Maj0r]

Use a BitSet instead of a bool array

[Botre]

Use a BitSet instead of a bool array

 

Thanks, I just learned something :x !