狂怒的狮子
2018-10-25 13:22
采纳率: 33.3%
浏览 1.3k

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;
}
  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • Italink 2018-10-25 14:14
    已采纳

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

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • Horken Kason 2018-10-25 14:10

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

    评论
    解决 无用
    打赏 举报
  • xingjianfengaa 2018-10-26 01:03

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

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题