|
找出100以內(nèi)的素?cái)?shù)
素?cái)?shù)定義：質(zhì)數(shù)，又稱素?cái)?shù)，指在一個(gè)大于1的自然數(shù)中，
除了1和此整數(shù)自身外，無法被其他自然數(shù)整除的數(shù)（也可定義為只有1和本身兩個(gè)因數(shù)的數(shù)）。
使用java.util.BitSet求素?cái)?shù)的算法：
例如要找100以內(nèi)的素?cái)?shù)，
1，聲明一個(gè)BitSet bs，第0,1位置false；其余位是true。
2，從2開始遍歷bs，如果是true就進(jìn)行內(nèi)循環(huán)遍歷。
3，內(nèi)循環(huán)遍歷：從外向內(nèi)環(huán)i開始遍歷bs，每次增長(zhǎng)一個(gè)i（這個(gè)很重要），把內(nèi)循環(huán)j在bs中的位置成false。
代碼如下
for(int i=0;i<bs.size();i++){
if(bs.get(i)){
//內(nèi)循環(huán)遍歷
for(int j=2*i;j<bs.size();j+=i){
bs.set(j, false);
}
}
}
（因?yàn)樗財(cái)?shù)只能被1和它本身整出，所以就把事它2倍，3倍，4倍....的數(shù)全過濾掉）
-
package com;
-
-
import java.util.BitSet;
-
-
public class mianTestSix {
-
-
/**
-
* @param args
-
*/
-
public static void main(String[] args) {
-
BitSet bs=new BitSet(100);
-
initBitSet(bs);
-
findSushuBitSet(bs);
-
printSushuBitSet(bs);
-
}
-
-
//第0,1位置成false，其余全部是true.
-
public static void initBitSet(BitSet bs){
-
for(int i=0;i<bs.size();i++){
-
if(i==0||i==1){
-
bs.set(i, false);
-
}else{
-
bs.set(i, true);
-
}
-
}
-
}
-
//處理數(shù)據(jù)，找到素?cái)?shù)
-
public static void findSushuBitSet(BitSet bs){
-
for(int i=0;i<bs.size();i++){
-
if(bs.get(i)){
-
//內(nèi)循環(huán)遍歷
-
for(int j=2*i;j<bs.size();j+=i){
-
bs.set(j, false);
-
}
-
}
-
-
}
-
}
-
//位是1的是素?cái)?shù)，打印
-
public static void printSushuBitSet(BitSet bs){
-
StringBuffer buf=new StringBuffer();
-
int num=0;
-
for(int i=0;i<100;i++){
-
if(bs.get(i)){
-
buf.append(i+",");
-
num++;
-
}
-
-
if((num+1)%20==0&&num!=0){
-
buf.append("\n");
-
}
-
}
-
System.out.println(buf.toString());
-
}
-
-
-
}
輸出：
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,
|
