质数概念：质数，又称素数，指在一个大于1的[自然数]中，除了1和此整数自身外，无法被其他自然数[整除]的数（也可定义为只有1和本身两个[因数]的数）。最小的素数是2，也是素数中唯一的[偶数]；其他素数都是[奇数]。质数有无限多个，所以不存在最大的质数。
public static void main(String[] args) {
// 求100以内的质数
for (int i = 2; i <= 100; i++) { // 质数
for (int k = 2; k <= i; k++) { // 除数
// 排除所有在 i=k 之前 能被k整除(余数为0)的数
if (i % k == 0 && i != k) {
break;
}
// 输出所有在 i=k 且 i%k=0的数
if (i % k == 0 && i == k) {
System.out.println(i);
}
}
}
}
1：根据定义去求解：也是最笨的方式，效率比较低
public static void main(String[] args) {
printPrime(1000);
}
public static void printPrime(int n){
for(int i = 2; i < n ; i++){
int count = 0;
for(int j = 2 ; j<=i; j++){
if(i%j==0){
count++;
}
if(j==i & count == 1){
System.out.print(i+" ");
}
if(count > 1){
break;
}
}
}
}
2：平方根
public static void main(String[] args) {
for(int j = 2; j<1000; j++){
if(m(j)){
System.out.print(j+" ");
}
}
}
public static boolean m(int num){
for(int j = 2; j<=Math.sqrt(num);j++){
if(num%j == 0){
return false;
}
}
return true;
}
3：找规律（摘自一个论坛讨论）
最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。质数有无限多个，所以不存在最大的质数。第三种方法说明了一个质数的特性：在所有质数中，只有2是偶数。
如果一个数能够被它之前的质数整除，那么这个数不是质数。
public class Primes {
public static void main(String[] args) {
// 求素数
List<Integer> primes = getPrimes(1000);
// 输出结果
for (int i = 0; i < primes.size(); i++) {
Integer prime = primes.get(i);
System.out.printf("%8d", prime);
if (i % 10 == 9) {
System.out.println();
}
}
}
/**
* 求 n 以内的所有素数
* @param n 范围
* @return n 以内的所有素数
*/
private static List<Integer> getPrimes(int n) {
List<Integer> result = new ArrayList<Integer>();
result.add(2);
for (int i = 3; i <= n; i += 2) {
if (!divisible(i, result)) {
result.add(i);
}
}
return result;
}
/**
* 判断 n 是否能被整除
* @param n 要判断的数字
* @param primes 包含素数的列表
* @return 如果 n 能被 primes 中任何一个整除，则返回 true。
*/
private static boolean divisible(int n, List<Integer> primes) {
for (Integer prime : primes) {
if (n % prime == 0) {
return true;
}
}
return false;
}
}
4.while循环
public static void main(String[] args) {
int i,n,k=0;
for (n = 3; n<=100; n++) { //3~100的所有数
i=2;
while (i<n) {
if (n%i==0)
break; //若能整除说明n不是素数，跳出当前循环
i++;
}
if (i==n) { //如果i==n则说明n不能被2~n-1整除，是素数
k++; //统计输出数的个数
System.out.print(i+ "\t ");
if (k %6==0) //每输出5个则换行
System.out.println();
}
}
}
