题目：
求1000以内的所有素数。
一、枚举
1、未优化代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
for(int i=2;i<1000;i++)
{
boolean b=true;
for(int j=2;j<=k;j++)
{
if(i%j==0)
{
b=false;
break;
}
}
if(b)
{
System.out.print(i+" ");
}
}
}
}
2、优化后代码（双层循环使用最少循环次数）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
System.out.print(2+" ");
for(int i=3;i<1000;i+=2)
{
boolean b=true;
int k=(int)java.lang.Math.sqrt(i);
for(int j=2;j<=k;j++)
{
if(i%j==0)
{
b=false;
break;
}
}
if(b)
{
System.out.print(i+" ");
}
}
}
}
二、筛法
思路：要求1000以内的所有素数，把2-1000这些数都列出来，2是素数，所有2的倍数都不是素数，划掉；取出下一个幸存的数，划掉它的所有倍数；直到所有幸存的数的倍数都被划掉为止。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n=1000;
boolean[] a=new boolean[n];
int k=(int)java.lang.Math.sqrt(n);
for(int i=2;i<=k;i++)
{
if(!a[i])
{
for(int j=i;j*i<n;j++)
{
a[i*j]=true;
}
}
}
for(int i=2;i<n;i++)
{
if(!a[i])
{
System.out.print(i+" ");
}
}
}
}
