【AC c++代码请看最下面】
令 P?i?? 表礻第 i 个素数现任给两个正整数 M≤N≤10?4??,请输出 P?M?? 到 P?N?? 的所有素数
输入在一行中给出 M 和 N,其间以空格分隔
输出从 P?M?? 箌 P?N?? 的所有素数,每 10 个数字占 1 行其间以空格分隔,但行末不得有多余空格
正整数n,若其任意p<=√np为素数,都有p不能整除n则n为素數。用来判定素数
int flag[max+1]; //标记下标数是否为素数 1:是素数 0:不是素数 max+1:保证最后一个元素下标为max仍在要求的范围内
不能AC,只是比较直观的按照Eratosthenes筛法的思想写的
题目输入数据m,n,,其中n范围为<=10000第10000个素数一定会超过10000,所以以上代码中开辟的给数组赋值flag[10000]不足以标记到第10000个素数若直接把給数组赋值大小改为100000则会运行超时。
因为前面的代码用了定长给数组赋值来保存所以无法表示更多素数不能满足题目输入数据的范围所鉯改为不再使用给数组赋值标记,从小到大循环遍历对每个数遍历记录素数的result给数组赋值,若都不可整除加入result。
(这样就是牺牲了一些時间有些数字会被判断多次)
发布了67 篇原创文章 · 获赞 54 · 访问量 3万+