求解素数问题算法

迷南。 2023-07-10 05:17 32阅读 0赞

## 问题的提出: ##

在解程序题的过程中经常会遇到素数的判断问题，在保证不能超时的同时要判断是否为素数，大多数初学者会采用第一种算法:  
1.（单单列出算法，不列出完整程序代码）

#include<stdio.h>
    #include<math.h>
    int f(int n)
    { 
    int i,j,test=0;
    for(i=2;i<1000000;i++)
    { 
    int a=0;
    for(j=2;j<=sqrt(i);j++)
    	{ 
    		if(i%j==0)
    		{ 
    			a=1;
    			break;
    		}
    	}
    if(a==0)
    test++;
    if(test==n)
    return i;
    }
    }

这就是求第n个素数的算法(姑且称之为算法，但是复杂度实在是太高了)，但是在跑代码的过程中，会发现经常出现超时的报错提醒，因为这个复杂度太大，达到了O(n\*2)，下面提供一种O(n)的求素数算法

## 问题的解决 ##

2.(仅提供算法，不提供完整程序)

#include<stdio.h>
    #include<iostream>
    #include<cmath>
    using namespace std;
    bool b[100000];
    int f()
    { 
    	int i;
    	for(i=1;i<100000;i++)
    	{ 
    		if(i%2)
    		b[i]=true;
    		else
    		b[i]=false;
    	}
    	b[2]=true;
    	for(i=3;i<100000;i++)
    	{ 
    		if(b[i])
    		{ 
    			for(int j=2*i;j<100000;j=j+i)
    			b[j]=false;
    		}
    	}
    }

##### 算法分析：这里面利用到的算法是如果n是素数，那么2n，3n等等一定就是合数，通过遍历一遍的方式来确定数是否是素数，同时在初始化的过程中，奇数的初始值全部设置为true，偶数的初始值全部设置为false，因为我们知道，除了2以外，所有的素数全部是奇数。算法的巧妙在于，在比较大的合数中，通过确定它的一个比较小的因子，就可以判断较大的数。节省了大量的运行时间，复杂度最大也就是个O(n^3/2),用一个bool类型的数组就将很大范围内的素数和合数都进行了判断。 #####

### 用某个跑的平台的评价证明算法的可行性(采用第一种算法会超时，采用第二种算法才能得到正确的答案)： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw_size_16_color_FFFFFF_t_70]

# 写作不易，点个赞再走呗。 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200229182151934.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw==,size_16,color_FFFFFF,t_70