题目描述
1.注释里i每次else都 加了两次。需要的还是用for循环吧
int findp(int n)
{
// int i=n+1;
// if(isprime(i))
// {
// if(isprime(i-6)) return i;
// else if(isprime(i+6)) return i;
// else i;
// }else i;
for (int i = n + 1; ; i++)
if (isprime(i) && (isprime(i - 6) || isprime(i + 6)))
return i;
}
for (int i = n + 1; ; i++)
if(isprime(i))
if(isprime(i-6)) return i;
else if(isprime(i+6)) return i;
2.没要求输出第几个素数,不用打表
不打表素数求法 10^5
int sqr=sqrt(n);
bool isprime(int n)
{
if(n<=1) return false;
int sqr=sqrt(n);
for(int i=2;i<=sqr;i++)
{
if(n%i==0) return false;
}
return true;
}
打表写法(埃式) 10^5 没问题
bool st[N];
int primes[N],cnt=0;
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[++cnt]=i;
for(int j=i+i;j<=n;j+=i)
st[j]=true;
}
}
}
get_primes(maxp);
样例
99993289
No
99993343
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+10;
int n;//primes[N];
//vector<int> primes;
//bool st[N];
bool isprime(int n)
{
if(n<=1) return false;
int sqr=sqrt(n);
for(int i=2;i<=sqr;i++)
{
if(n%i==0) return false;
}
return true;
}
int findp(int n)
{
// int i=n+1;
// if(isprime(i))
// {
// if(isprime(i-6)) return i;
// else if(isprime(i+6)) return i;
// else i++;
// }else i++;
for (int i = n + 1; ; i++)
if (isprime(i) && (isprime(i - 6) || isprime(i + 6)))
return i;
}
int main()
{
//freopen("1.txt","r",stdin);
//cin>>n;
n=99993289;
if(isprime(n))
{
if(isprime(n-6)) cout<<"Yes"<<endl<<n-6;
else if(isprime(n+6)) cout<<"Yes"<<endl<<n+6;
else cout<<"No"<<endl<<findp(n);
}else cout<<"No"<<endl<<findp(n);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla