1007 素数对猜想 (20 分),我的程序只能拿4分,试了很多例子也没发现错误,不知道为何

题目:
PAT 1007 素数对猜想 (20 分)
“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<10^5 ),请计算不超过N的满足猜想的素数对的个数。

输入格式:
输入在一行给出正整数N。

输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:
20
输出样例:
4

 #include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int n;
    cin >> n;
    bool *primes=new bool[n+1];
    memset(primes, 1, sizeof(bool)*(n+1));
    primes[0] = primes[1] = 0;
    int count = 0;
    for (int i = 2; i <=n; i++)
    {
        if (primes[i])
        {
            if (primes[i - 2])
                count++;
            for (int j = i + i; j <= n; j = j + i)
                primes[j] = 0;
        }

    }
    cout << count << endl;
    return 0;
}
0

3个回答

我这里并没有出现错误,楼主的测试点报错信息是什么
图片说明

0
wangqifeng01
狂怒的狮子 我估计是昨天系统升级有问题,同样的代码,我今天早上过了
10 个月之前 回复

你的算法时间复杂度o(n^2),题目n最大10^5,就是10^10,100亿了,肯定超时。可以用“线性素数筛选”,实在过不了,再打一个表。

0
wangqifeng01
狂怒的狮子 我是用的快速筛法
10 个月之前 回复

首先,C++里 一般不考虑 new来创建,直接用数组对象,因为你new出来 的一定要delete,否则有内存泄漏,还有就是让你遍历的时候,最好不要用什么 i=3;i<100;i++之类的,比如你用i=3;i<100;i+=2;是偶数的都跳过,这样最起码少了一半的循环,只是一个小的举例,这个你可以自己去思考,循环最好是尽可能的减少循环次数

0
wangqifeng01
狂怒的狮子 嗯,受教。
10 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
1007 素数对猜想 (20)(20 分)
1007 素数对猜想 (20)(20 分) 让我们定义 d~n~ 为:d~n~ = p~n+1~ - p~n~,其中 p~i~ 是第i个素数。显然有 d~1~=1 且对于n&amp;amp;gt1有 d~n~ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N (&amp;lt; 10^5^),请计算不超过N的满足猜想的素数对的个数。 输入格式:每个测试输入包含1个测试用例,...
1007 素数对猜想 (20 分)(C语言实现)
1007 素数对猜想 (20 分) 让我们定义d​n为:dn=p​n+1−p​n,其中p​i是第i个素数。显然有d​1=1,且对于n&amp;gt;1有d​n是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10​^5​​ ),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。...
C++ 1007 素数对猜想(20 分)
  思路: 1:求出1到N之间的素数 2:判断满足条件的素数对个数   注意:for(j=2;j&amp;lt;=sqrt(i);j++)  有等号,否则会出错。 #include&amp;lt;iostream&amp;gt; #include&amp;lt;cmath&amp;gt; //sqrt() using namespace std; int main() { int i,j,cnt=0; int...
python3之1007.素数对猜想 (20分)
题目赘述如下: 让我们定义 dn为:dn= pn+1- pn,其中 pi是第i个素数。显然有 d1=1 且对于n&gt;1有 dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N (&lt; 10^5),请计算不超过N的满足猜想的素数对的个数。 输入格式:每个测试输入包含1个测试用例,给出正整数N。 输出格式:每个测试用例的输出占一行,不超过N的...
1007. 素数对猜想 (20)(java实现)
最开始提交的时候最后一组数据一直运行超时,相同代码换成c++也是,百思不得其解。。最后上课的时候想到判断是否是素数的时候,自己之前循环的num/2,但其实到100000就要循环5000次,之前刚开始写的时候没有考虑数比较大的情况,但其实循环到num的平方根,num比较大循环的次数就少很多了。为什么可以循环到数的平凡根就可以了->https://zhidao.baidu.com/question/7
1007 素数对猜想(20 分)通俗详解
本题链接:https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744 让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&amp;gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;...
7-3 素数对猜想(20 分)
让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&amp;gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。...
1007 素数对猜想 (20)(20 分) C++ 小白的小技巧
题目简单到夸张!不吃辣条~1007 素数对猜想 (20)(20 分)让我们定义 d~n~ 为:d~n~ = p~n+1~ - p~n~,其中 p~i~ 是第i个素数。显然有 d~1~=1 且对于n&amp;amp;gt1有 d~n~ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N (&amp;lt; 10^5^),请计算不超过N的满足猜想的素数对的个数。输入格式:每个测试输入包含...
1007. 素数对猜想 解决python超时问题
此题如果采用素数的定义来判别,将会超时,因此采用素数筛选法 核心思想:素数的倍数一定不是素数 偶数一定不是素数 从2开始依次往后面数,如果当前数字一个素数,那么就将所有其倍数的数从表中删除或者标记,然后最终得到所有的素数。 详细的解释可以看一下这位大大的博文 https://blog.csdn.net/power721/article/details/8216619 本文主要采用一种写法...
1007 素数对猜想 (20 分)
**1007 素数对猜想 (20 分) 让我们定义d ​n ​​ 为:d ​n ​​ =p ​n+1 ​​ −p ​n ​​ ,其中p ​i ​​ 是第i个素数。显然有d ​1 ​​ =1,且对于n&amp;amp;gt;1有d ​n ​​ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;amp;lt;10 ​5 ​​ ),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在...
1007 素数对猜想 (20 分)java
让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。输入格式: 输入在一行给出正整数N。输出格式: ...
PAT--1007 素数对猜想(20 分)
1007 素数对猜想(20 分) 让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&amp;gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输...
[PAT乙级]1007. 素数对猜想 (20)
1007. 素数对猜想 (20)原题链接 让我们定义 dn 为:dn = pn+1 - pn,其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N (< 105),请计算不超过N的满足猜想的素数对的个数。输入格式:每个测试输入包含1个测试用例,给出正整数N。输出格式:每个测试用例的输出占一行,不超过N的满
PAT1007 素数对猜想(20)
“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
1007素数对猜想 java实现
import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner scan = new Scanner(System.in); int input = scan.nextInt(); scan.close(); int sushu[] = new int[10...
1007-素数对猜想 (20)
让我们定义dn为:dn =pn+1−pn ,其中pi​​ 是第i个素数。显然有d1​​ =1,且对于n&amp;gt;1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。   现给定任意正整数N(&amp;lt;10^5 ),请计算不超过N的满足猜想的素数对的个数。   输入格式: 输入在一行给出正整数N。   输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。   ...
1007 素数对猜想(20 分)提问
让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&amp;gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。...
自测-2 素数对猜想(20 point(s))
  让我们定义d​n​​为:,其中p​i​​是第i个素数。显然有,且对于有是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数(&amp;lt;),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数。 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。 输入样例: 20 输出样例: 4 【c code】 #incl...
PAT 1007 素数对猜想 --思路比较重要,想清楚再动手
素数对猜想 让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n>1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的
PAT 1007. 素数对猜想 python 运行超时问题解决方案
判断素数的方法举例,不止是 sqrt()
1007 素数对猜想 (20 分) Java练习&PTA乙级 Vector应用
题意:问不超过n的所有数中,相邻素数差值为2的个数 解: 素数打表(筛法),然后存进 Vector 中,扫一遍 1. java中Vector的应用,类似于STL中的vector import java.lang.reflect.Array; import java.math.BigDecimal; import java.math.BigInteger; import...
1007 素数对猜想(PAT 乙级 C++实现)
1007 素数对猜想让我们定义 d~n~ 为:d~n~ = p~n+1~ - p~n~,其中 p~i~ 是第i个素数。显然有 d~1~=1 且对于n&amp;amp;gt1有 d~n~ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N (&amp;lt; 10^5^),请计算不超过N的满足猜想的素数对的个数。输入格式:每个测试输入包含1个测试用例,给出正整数N。输出格式:每个测试用...
PTA: 7-1 素数对猜想 (20 分) (考点:如何高效率判断素数)
都怪我没积极看MOOC,这题我考试瞪了一个小时,最后一个点永远超时,没别的思路 思路一: (数组不是个好思路,因为N的值可能很大,那样的话需要定义的数组也得很大,而且没有准确的上限) ——先判断素数,存入数组,再作差,再判断 #include&amp;amp;lt;stdio.h&amp;amp;gt; int main() { int a[100]; int t1,N,t,n=0,c,t3=0; sc...
自测-2 素数对猜想(20 分)
让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&amp;gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N(&amp;lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。输入格式:输入在一行给出正整数N。输出格式:在一行中输出不超过N的满足猜想的素数对的个数。输入样例:20 输出...
C语言实现三子棋
C语言简单实现三子棋#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include<string.h> #include <stdlib.h> #include <time.h>#define ROWS 3 #define COLS 3 void menu()//菜单函数,输出可供选择的菜单 { printf("************
1007 素数对猜想(C语言版 + 注释 + 素数)
1007 素数对猜想(20 分) 让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&amp;gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输...
自测-2 素数对猜想 (20分)
让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n>1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。
【C/C++】素数对猜想
自测-2 素数对猜想(20 分) 让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n>1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一
素数对猜想
让我们定义 dn 为:dn = pn+1 - pn,其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N (< 105),请计算不超过N的满足猜想的素数对的个数。输入格式:每个测试输入包含1个测试用例,给出正整数N。 输出格式:每个测试用例的输出占一行,不超过N的满足猜想的素数对的个数。输入样例:
PAT 1007 素数对猜想 C++(解决最后一测试点超时)
让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&amp;gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。...
PAT B1007题解
1007 素数对猜想 (20 分) 让我们定义d ​n ​​ 为:d ​n ​​ =p ​n+1 ​​ −p ​n ​​ ,其中p ​i ​​ 是第i个素数。显然有d ​1 ​​ =1,且对于n&amp;gt;1有d ​n ​​ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10 ​5 ​​ ),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一...
PAT乙级Java实现_1007. 素数对猜想 _附详细解题注释_07
1007. 素数对猜想 (20)时间限制400 ms内存限制65536 kB代码长度限制8000 B判题程序Standard作者CHEN, Yue让我们定义 dn 为:dn = pn+1 - pn,其中 pi 是第i个素数。显然有 d1=1 且对于n&amp;gt;1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N (&amp;lt; 105),请计算不超过N的满足猜想的...
Pta1007素数对猜想 (20)
#include #include using namespace std; int main() {     int N=0;     cin>>N;     int cal=0;//计数;     int temp[110000]={0};     int x=0;     bool flag=true;     for(int i=2;i     {       
PTA 7-2 素数对猜想 (20 分)
让我们定义dn=pn+1-pn,其中p​i是第i个素数。素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N(&lt;10​0000​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。 输入样例: 20 输出样例: 4 #include&lt;bits/stdc++.h&gt; u...
PTA 1007 素数对猜想
让我们定义d​n​​ 为:d​n​​ =p​n+1​​ −p​n​​ ,其中p​i​​ 是第i个素数。显然有d​1​​ =1,且对于n&amp;gt;1有d​n​​ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10​5​​ ),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的满足猜想的素数对的...
5-27 素数对猜想 (20分)
5-27 素数对猜想   (20分) 让我们定义d_nd​n​​为:d_n = p_{n+1}-p_nd​n​​=p​n+1​​−p​n​​,其中p_ip​i​​是第ii个素数。显然有d_1 = 1d​1​​=1,且对于n>1n>1有d_nd​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(10​5​​),请计算不超过N的满足猜
7-1 素数对猜想 (20 分) (PAT练习题,做完之后列出一些大家可能得不到满分的细节条件,个人经验,仅供参考)
让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。...
1007 素数对猜想——C++实现
题目 1007 素数对猜想 (20 point(s)) 让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n&amp;gt;1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(&amp;lt;10​5​​),请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。 ...
PAT乙级1007. 素数对猜想(C语言)
PAT乙级真题题解目录 /* * 1. 相邻且差为2的素数对 的筛选有两种思路: * - 判断两个相邻的素数 差值是否为2 (伪) * - 判断差值为2的两个数是否为素数 * 即使采用第一种思路,但筛选素数本身就是第二种思路。 * 2. 素数有:2、3、5、7... * 可知,第一对素数对为 (3, 5); * 由于题目给出数值 &amp;lt;= N,则素...
1007. 素数对猜想 (20)
本题要求:让我们定义 dn 为:dn = pn+1 - pn,其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N (< 105),请计算不超过N的满足猜想的素数对的个数。输入格式:每个测试输入包含1个测试用例,给出正整数N。输出格式:每个测试用例的输出占一行,不超过N的满足猜想的素数对的个数。输入样例:2