素数 题解:不用素数筛
首先数据范围不是很大,即使是纯粹的暴力遍历复杂度大概在n*sqrt(n),应该是不会超时,但数据量增加的情况下暴力判定是不是素数就会超时。普遍的解法一般是素数筛筛出1—n的素数x,然后判断x%10 == 1,尾数为1输出。但是有没有不用背并且复杂度不高的算法可以直接解决问题呢?打表!
先美美的写一个暴力到不能再暴力的代码输出10000以内所有的素数:
#include<bits/stdc++.h>
using namespace std;
bool su(int n){
if(n <= 1) return false;
if(n == 2) return true;
bool flag = true;
for(int i = 2; i <= sqrt(n);i++){
if(n%i == 0){
flag = false;
break;
}
}
if(flag) return true;
else return false;
}
int main(){
for(int i = 1;i <= 10000;i++){
if(su(i)){
&n...
登录后发布评论
暂无评论,来抢沙发