这是我根据http://blog.csdn.net/program_think/article/details/7032600写出的试除发，但是筛选法我却写不出来，求高人指定写，或推荐类似的书给我看看！谢谢…… /**
* 查找100以内的质数
*/
ArrayList<Integer> primeNumber = new ArrayList<Integer>();
lable: for (int i = 2; i < 100; i++) {
if (i == 2 || i % 2 != 0) { // 质数是除2以外的奇数
int sqrt = (int) Math.sqrt(i);// 一个数如果是合数，那么它的所有的因子不超过它的开方
for (int j = 0, h = primeNumber.size(); j < h; j++) {
// 获得已经得到的质数
int number = primeNumber.get(j);
// 能被平方根以内的质数整数的都是合数
if (number > sqrt || i % number == 0) {
continue lable;
}
}
primeNumber.add(i);
}
}
* 查找100以内的质数
*/
ArrayList<Integer> primeNumber = new ArrayList<Integer>();
lable: for (int i = 2; i < 100; i++) {
if (i == 2 || i % 2 != 0) { // 质数是除2以外的奇数
int sqrt = (int) Math.sqrt(i);// 一个数如果是合数，那么它的所有的因子不超过它的开方
for (int j = 0, h = primeNumber.size(); j < h; j++) {
// 获得已经得到的质数
int number = primeNumber.get(j);
// 能被平方根以内的质数整数的都是合数
if (number > sqrt || i % number == 0) {
continue lable;
}
}
primeNumber.add(i);
}
}
public class Prime {
public static void main(String[] args) {
int i, j, s, d = 0;
for (i = 1; i < 100; i++) {
s = 0;
for (j = 1; j <= i; j++) {
if (i % j == 0) {
s += 1;
}
}
if (s == 2) {
System.out.println(i);
d = d + 1;
}
}
System.out.println("100以内的质数有: " + d + " 个");
}
}
public static void main(String[] args) {
//循环100以内的数
for (int n=1;n<=100;n++){
//给b初始值true
boolean b = true;
//如果循环拿到的数n不等于1，就进入下面循环
if (n != 1 ){
//i从大于1的第一个数也就是2开始，一次循环到比这个数n本身小的最大的数
//何为质数，除了1和他本身不能再被其他数整除。所以...这样循环
for (int i = 2; i < n; i++){
if (n % i == 0){//如果取余为0，也就是除了1和其本身有其他数可以乘除他，所以置为false
b = false;
//跳出当前循环，判断是否打印，并且到外面循环继续
break;
} }
}
//如果b为true打印下面的质数
if (b){
System.out.println(n + "是质数");
}
}
}
}
public static void main(String[] args) {
boolean[] bools = new boolean[101];
// 初始化
for (int i = 0; i < 101; i++) {
bools[i] = true;
}
//筛选法求素数
for (int i = 2; i < 101; i++) {
if (bools[i]) {
for (int j = i + 1; j < 101; j++) {
if (j %i==0)
{
bools[j] = false;
}
}
}
}
//打印结果
for (int i = 2; i < 101; i++) {
if(bools[i])
{
System.out.println(i);
}
}
}
public class T1 {
/**
* @param args
*/
public static void main(String[] args) {
int[] a=new int[100];
for(int i=0;i<100;i++){
a[i]=1;
}
for(int i=2;i<100;i++){
if(a[i]!=0){
for(int j=i+i;j<100;){
if(j%i==0){
a[j]=0;
j=j+i;
}
}
}
}
for(int i=2;i<100;i++){
if(a[i]!=0) {
System.out.println(i);
}
}
}}
筛选吧，就是先讲素数的倍数剔除。定义一个101长度的数组，
从下标2开始，第一次将2的倍数剔除，然后将3的倍数剔除，就这样循环....试着debug一下就知道了。
boolean[] b = new boolean[101];
// 筛选法求素数
for (int i = 2; i < 101; i++) {
if (b[i]==false) {
for (int j = i *2; j < 101; j+=i) {
b[j] = true;
}
}
}
// 打印结果
for (int i = 2; i < 101; i++) {
if (b[i]==false) {
System.out.println(i);
}
}这样可以吗？
long aaaa=System.currentTimeMillis();
LinkedList<Integer> l3 = new LinkedList<Integer>();
byte[] by = new byte[100001];
// 筛选法求素数
for (int i = 2; i < 100001; i++) {
if (by[i] == 0) {
for (int j = i * 2; j < 100001; j += i) {
by[j] = 1;
}
}
}
// 打印结果
for (int i = 2; i < 100001; i++) {
if (by[i] == 0) {
l3.add(i);
}
}
long bbbb=System.currentTimeMillis();
System.out.println("第三种byte运行时间："+(bbbb-aaaa));
long t0, t1;
t0 = System.nanoTime();
boolean b = !isComposite(479001599);
boolean c = !isComposite(456789012);
t1 = System.nanoTime();
System.out.println(t1 - t0);
System.out.println(b + " " + c);
} /**
* <p>Miller-Rabin 测试某一个数是否是合数</p>
*
* @param n 需要测试的数
* @return true: 该数为合数；false: 该数为素数
*/
public static boolean isComposite(int n) {
if (n < 2) {
throw new IllegalArgumentException("number must greater than or equals 2");
}
// 排除 2、3、5、7 以加速测试
if (n == 2 || n == 3 || n == 5 || n == 7) {
return false;
} // 偶数
if ((n & 1) == 0) {
return true;
} // 排除 3、5、7 的倍数，以加速测试
if (n % 3 == 0) {
return true;
}
if (n % 5 == 0) {
return true;
}
if (n % 7 == 0) {
return true;
} // 寻找 s 和 d 以满足 n = 2^s * d + 1
int s = 0, d = n - 1;
while ((d & 1) == 0) {
d >>= 1;
s++;
} // 对于各种数值需要进行 Miller-Rabin 基准测试的素数值
// 参考：http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test
// if n < 1,373,653, it is enough to test a = 2 and 3;
// if n < 9,080,191, it is enough to test a = 31 and 73;
// if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
// if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;
// if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;
// if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17. if (n < 1373653) {
if (loopMillerRabin(s, d, n, 2, 3)) {
return true;
}
} else if (n < 9080191) {
if (loopMillerRabin(s, d, n, 31, 73)) {
return true;
}
} else {
// 4,759,123,141 已经超过 int 的最大值，因此大于等于 9080191 就采用 4,759,123,141 的基准测试
if (loopMillerRabin(s, d, n, 2, 7, 61)) {
return true;
}
}
return false;
} /**
* <p>循环 Miller-Rabin 测试</p>
*
* @param s n = 2^s * d + 1 中的 s 值
* @param d n = 2^s * d + 1 中的 d 值
* @param n 需要测试的数
* @param t 测试的基准素数
*/
private static boolean loopMillerRabin(int s, int d, int n, int... t) {
for (int i = 0; i < t.length; i++) {
if (testMillerRabin(t[i], s, d, n)) {
return true;
}
}
return false;
} /**
* <p>Miller-Rabin 基本测试</p>
*
* @param a 素性测试基准素数
* @param s n = 2^s * d + 1 中的 s 值
* @param d n = 2^s * d + 1 中的 d 值
* @param n 需要测试的数
* @return 测试某一数是否是合数。true: 该数是合数；false: 该数可能是素数。若返回 false
* 需要进行多基准的联合测试才能判断该数确实是素数
*/
private static boolean testMillerRabin(int a, int s, int d, int n) {
if (montgomery(a, d, n) != 1) {
int e = 1;
for (int i = 0; i < s; i++) {
if (montgomery(a, d * e, n) + 1 == n) {
return false;
}
e <<= 1;
}
return true;
}
return false;
} /**
* <p>使用 Montgomery 算法计算 (base ^ exp) % mod 的值。</p>
*
* <p>由于 Java 中 int 的运算速度远远大于 long 的运算速度，因此该算法需要改进！</p>
*
* @param base 基数
* @param exp 指数
* @param mod 模数
*/
private static int montgomery(int base, int exp, int mod) {
if (base > 46340 || mod > 46340) {
long temp = 1;
long prod = base % mod;
while (exp > 1) {
if ((exp & 1) != 0) {
temp = (temp * prod) % mod;
}
prod = (prod * prod) % mod;
exp >>= 1;
}
return (int) ((temp * prod) % mod);
} else {
int temp = 1;
int prod = base % mod;
while (exp > 1) {
if ((exp & 1) != 0) {
temp = (temp * prod) % mod;
}
prod = (prod * prod) % mod;
exp >>= 1;
}
return (temp * prod) % mod;
}
} /**
* <p>
* 根据复化辛普生法则计算高斯 Li 函数。Li(x) 近似于素数个数函数 π(x)
* </p>
*
* @param x 数值范围
* @return 该值以内的素数个数的估计值
*/
private static double gaussLi(int x) {
int n = x;
double s = 2;
double h = (x - s) / n;
double a = f(s + h / 2);
double b = 0;
for (int k = 1; k < n; k++) {
a += f(s + k * h + h / 2);
b += f(s + k * h);
}
return (h / 6) * (f(s) + 4 * a + 2 * b + f(x));
} /**
* <p>
* Guass Li(x) 积分函数项
* </p>
*
* @param x
* @return
*/
private static double f(double x) {
return 1 / Math.log(x);
}
}
* 查找100以内的质数
*/
ArrayList<Integer> primeNumber = new ArrayList<Integer>();
lable:
for (int i = 2; i < 100; i++) {
if (i==2||i%2!=0) { //质数是除2以外的奇数
int sqrt = (int)Math.sqrt(i);//一个数如果是合数，那么它的所有的因子不超过它的开方
for (int j = 0,h = primeNumber.size(); j < h; j++) {
//获得已经得到的质数
int number = primeNumber.get(j);
//能被平方根以内的质数整数的都是合数
if (number>sqrt|| i%number==0) {
continue lable;
}
}
primeNumber.add(i);
}
}
推荐二进制位运算的经典书籍 Henry S. Warren 的 Hacker's Delight，中文版《高效程序的奥秘》。
for (int i = 2; i < n; i++){
if (n % i == 0){//如果取余为0，也就是除了1和其本身有其他数可以乘除他，所以置为false
b = false;
//跳出当前循环，判断是否打印，并且到外面循环继续
break;
}
既然当n % i == 0的时候就是false，即退出了for loop，那么一开始i=2的时候n % i == 0也是成立的，那么b也就为false了，但为啥最后输出结果里面还有2呢？