Skip to content

Instantly share code, notes, and snippets.

@yokolet
Created September 5, 2019 05:28
Show Gist options
  • Save yokolet/6a16de49404c7306019b052cdb7b9401 to your computer and use it in GitHub Desktop.
Save yokolet/6a16de49404c7306019b052cdb7b9401 to your computer and use it in GitHub Desktop.
import java.util.*;
public class PrimeNumber {
private List<Integer> sieve(int m) {
List<Integer> p = new ArrayList<Integer>();
if (m <= 1) { return p; }
boolean[] ary = new boolean[m+1];
Arrays.fill(ary, 2, m+1, true);
for (int i = 2; i <= m; i++) {
if (ary[i]) {
p.add(i);
for (int j = i * 2; j <= m; j += i) {
ary[j] = false;
}
}
}
return p;
}
private boolean checkPrime(int n, List<Integer> p) {
if (p.size() == 0) { return true; }
for (int i = p.size()-1; i >= 0; i--) {
if (n % p.get(i) == 0) { return false; }
}
return true;
}
public String isPrime(int n) {
if (n <= 1) { return "Not prime"; }
int m = (int)Math.sqrt(n);
List<Integer> primes = sieve(m);
return checkPrime(n, primes) ? "Prime" : "Not prime";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment