package site.iknown.farm.test;
public class Main
{
private static int isPrime(int n)
{
for(int i=2;i<=Math.sqrt(n);i++)
{
if(n%i == 0)
{
return 0;
}
}
return 1;
}
private static int normalPrimes(int n)
{
int sum = 0;
for(int i=2;i<n;i++)
{
sum += isPrime(i);
}
return sum;
}
private static int betterPrimes(int n)
{
int array[] = new int[n];
for(int i=2;i<array.length;i++)
{
array[i] = 1;
}
for(int i=2;i<array.length;i++)
{
if(array[i] == 1)
{
for(int j=2;i*j<array.length;j++)
{
array[i*j] = 0;
}
}
}
int sum = 0;
for(int i=2;i<array.length;i++)
{
sum += array[i];
}
return sum;
}
public static void main(String[] args)
{
for(int i=2;i<10;i++)
{
long normalStart = System.currentTimeMillis();
int sum = normalPrimes((int)Math.pow(10, i));
long normalEnd = System.currentTimeMillis();
System.out.println("素数统计结果:"+"0-"+Math.pow(10, i));
System.out.println("普通方法：");
System.out.print(sum+"个");
System.out.println((normalEnd - normalStart)+"毫秒");
long betterStart = System.currentTimeMillis();
int reSum = betterPrimes((int) Math.pow(10, i));
long betterEnd = System.currentTimeMillis();
System.out.println("筛法：");
System.out.println(reSum+"个");
System.out.println((betterEnd - betterStart)+"毫秒");
}
}
}
运行分析：
数据范围比较小的时候两种方法差不多，但是对于数据范围比较大尤其是大于pow(10,5)时候，效率明显看出了不同。
