设计 求不超过正整数n的最大素数 的程序框图

用筛选法，令f初值为0，从i=2开始，若f(i)=0,则将1-n内所有i的倍数（除i以外）的f赋为1，否则跳过，然后由n向1找出第一个f为0的数字，则该数字为所求（时间效率

o（2n），空间效率o(n)，较枚举每个数字并判断更快）

附c++代码

#include

#include

using

namespace

std

int

main(int

argc,

char

*argv[])

{

int

f[1000000],i,r

int

n

memset(f,0,sizeof(f))//初值赋为0

cout<<"请输入n"<

>n

for(i=2i<=ni++)

{

if(f[i]==1)

continue//如果f为1，跳过

r=i*2

//从2倍开始

while(r<=n)

//找小于n的数

{

f[r]=1

r+=i

}

}

for(i=ni>=2i--)

if(f[i]==0)

{

cout<<"在1-n中最大的质数是："<

评论

0

0

加载更多

def is_prime(m):

"""判断m是否素数"""

if m <2:

return False

for i in range(2, int(m**(1/2))+1):

if m % i == 0:

return False

return True

# 求100到200之间所有素数

t = []

for i in range(101, 200, 2):

if is_prime(i):

t.append(i)

print(f'100到200之间所有素数')

print(t)

程序缩进如图所示

循环嵌套，外层循环是从1-1000的数字i（1排除，这你应该明白），内层是对数字i的素数判断。

素数：除了1和它本身外没有别的因子。也可以理解为：除了1和它本身，其他数来除它余数都不是0。

所以内层循环用从2开始到i的平方根（取整）依次求余，因为到了平方根以后，再增加除数，得到的商是小于平方根的，等于以前取过的除数。所以平方根以后不用再算了。

如果有=0的余数（if（i%j ==0）），说明正在判断的数字不是素数，用break语句退出内层循环；如果没有=0的余数，开关数w不归零，if（w）后的语句执行，计数器n自加一次（找到一个素数），并打印当前检验数i。

打印前有一个if判断，如果计数器n满整10（能够被10整除）就换行，也就是说这个素数表每行10个数。不换行数字键隔一个列表间隔（等于tab）。

#include <stdio.h>

#include <math.h>

void main()

{ int n=0, i, j,w,k

for(i=2i<=1000i++)

{w=1

k=sqrt(i)

for (j=2j<=kj++)

if (i%j==0)

{w=0break}

if (w)

{

++n

if (n%10==0) printf("%d\n",i)

else printf("%d\t",i)

}

}

}

---