Jump to content

Sieve of Eratosthenes & Primality test


Botre

Recommended Posts

Not super useful for scripting, but here you go.

 

Sieve_of_Eratosthenes_animation.gif

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
Link to comment
Share on other sites

WOW. Ive just lost all my respect for you... doge.pngQwPha8E.png

 

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 :doge:

Edited by Botre
  • Like 1
Link to comment
Share on other sites

 

Not super useful for scripting, but here you go.

 

Sieve_of_Eratosthenes_animation.gif

/**
 * @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? :s

Link to comment
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?

Link to comment
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?

Link to comment
Share on other sites

  • 2 weeks later...

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...