100000以内素数java实验结果截图_寻找100000以内素数（质数）

亦凉 2022-11-06 01:49 148阅读 0赞

方法一

简单的质数寻找就是对1~100000的数进行遍历

方法二

这样的遍历复杂度为O(n2)

进行优化就可以发现偶数不可能为质数，因此质数也不可能含有偶数因子

方法三

经过计算发现所有的质数都满足4x+1或者4x-1

因此将其命名为模4遍历法

方法四

与方法三类似，创建了模6遍历法

以下是源代码

import java.util.ArrayList;

import java.util.List;

/\*\*

\* Author: samsung

\* Date: 04/12/2019

\* Email: \*\*\*\*\*\*\*\*@foxmail.com

\*\*/

public class PrimeSearch \{

public static void main(String\[\] args)\{

//寻找100000以内所有质数

//暴力搜索

long start1=System.currentTimeMillis();

List list1=new ArrayList<>();

list1.add(2);

for(int i=3;i<=100000;++i)\{

boolean flag=true;

for(int k=2;k

if(i%k==0)\{

flag=false;

break;

if(flag)list1.add(i);

System.out.println("暴力傻子式遍历法：");

System.out.println("共找到质数"+list1.size()+"个，耗时"+(System.currentTimeMillis()-start1)+"ms");

//排除偶数

long start2=System.currentTimeMillis();

List list2=new ArrayList<>();

list2.add(2);

for(int i=3;i<100000;i+=2)\{

boolean flag=true;

for(int k=3;k

if(i%k==0)\{

flag=false;

break;

if(flag)list2.add(i);

System.out.println("排除偶数和偶数因子遍历法：");

System.out.println("共找到质数"+list2.size()+"个，耗时"+(System.currentTimeMillis()-start2)+"ms");

//继续优化发现除2以外，其他质数均满足4x-1或者4x+1

//因此做出以下测试

long start3=System.currentTimeMillis();

List list3=new ArrayList<>();

list3.add(2);

int m=0,n=0;

for(int i=1;m<100000||n<100000;++i)\{

m=4\*i-1;n=4\*i+1;

if(m<100000)\{

boolean flag=true;

for(int k=3;k

if(m%k==0)\{

flag=false;

break;

if(flag)list3.add(m);

if(n<100000)\{

boolean flag=true;

for(int k=3;k

if(n%k==0)\{

flag=false;

break;

if(flag)list3.add(n);

System.out.println("模4遍历法：");

System.out.println("共找到质数"+list3.size()+"个，耗时"+(System.currentTimeMillis()-start3)+"ms");

//继续优化发现除2,3以外，其他质数均满足6x-1或者6x+1

//因此做出以下测试

long start4=System.currentTimeMillis();

List list4=new ArrayList<>();

list4.add(2);

list4.add(3);

m=0;n=0;

for(int i=1;m<100000||n<100000;++i)\{

m=6\*i-1;n=6\*i+1;

if(m<=100000)\{

boolean flag=true;

for(int k=3;k

if(m%k==0)\{

flag=false;

break;

if(flag)list4.add(m);

if(n<=100000)\{

boolean flag=true;

for(int k=3;k

if(n%k==0)\{

flag=false;

break;

if(flag)list4.add(n);

System.out.println("模6遍历法：");

System.out.println("共找到质数"+list4.size()+"个，耗时"+(System.currentTimeMillis()-start4)+"ms");

运行结果是

暴力傻子式遍历法：

共找到质数9592个，耗时1674ms

排除偶数和偶数因子遍历法：

共找到质数9592个，耗时661ms

模4遍历法：

共找到质数9592个，耗时661ms

模6遍历法：

共找到质数9592个，耗时655ms

由此得出结论，排除偶数因子的方法和模6模4遍历法速度基本一致

100000以内素数java实验结果截图_寻找100000以内素数（质数）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关筛选100以内的素数

相关 python 输出100以内的质数（素数）

相关 java算法：求100以内的素数

相关 100000以内素数java实验结果截图_寻找100000以内素数（质数）

相关计算100以内的素数

相关循环打印100以内的素数

相关打印100以内的素数

相关打印100以内的素数

相关 100以内的质数（素数）

相关 Java 输出100以内的可逆素数（质数）（方法1 直接输出）