素数問題高速判定アルゴリズム
2042 ワード
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* , 。 1-100 ,
* 1-10 [2,3,5,7],
* 11-100 %[2,3,5,7],
*/
public class Prime {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(" ( a b):");
while (true) {
long n1 = sc.nextLong();
long n2 = sc.nextLong();
List<Long> primeList = getPrime(n1, n2);
for (Long prime : primeList) {
System.out.print(prime + " ");
}
System.out.println();
}
}
public static List<Long> getPrime(long begin, long end) {
List<Long> result = new ArrayList<Long>();// result begin-end
List<Long> tempPrime = new ArrayList<Long>();// 2-Math.sqrt(end)
for (long i = 2; i <= Math.sqrt(end); i++) {
if (isPrime(i)) {
tempPrime.add(i);
// System.out.print(i + " ");
}
}
// System.out.println();
for (long prime : tempPrime) {
if (prime >= begin) {
result.add(prime);
}
}
long start = (long) Math.sqrt(end);
if (start > begin) {
begin = start;
}
for (long i = begin; i <= end; i++) {
boolean flag = true;
for (long prime : tempPrime) {
if (i % prime == 0) {
flag = false;
break;
}
}
if (flag) {
result.add(i);
}
}
return result;
}
/**
*
*/
public static boolean isPrime(long n) {
for (long i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
if (n <= 1L) {
return false;
}
return true;
}
}