【练习】腾讯2017秋招笔试编程题——3. 素数对

给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。
如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）

输入描述:

输入包括一个整数n,(3 ≤ n < 1000)

输出描述:

输出对数

输入例子1:

输出例子1:

题目链接： https://www.nowcoder.com/question/next?pid=5582994&qid=105228&tid=21974697

#include <iostream>

using namespace std;

#define MAX 1005

int prime[MAX];
int prime_num;

int chooseprime()
{
    int p[MAX];
    for(int i=0;i<MAX-1;i++)
        p[i]=1;
    p[0]=p[1]=0;
    int cnt=0;
    for(int i=2;i<=MAX-1;i++)
    {
        if(p[i]==1)
        {
            prime[cnt++]=i;
            for(int j=2*i;j<=MAX-1;j=j+i)
                p[j]=0;//Μή³ύ±ΆΚύ
        }
    }
    return cnt;
}

int is_num(int x)
{
    for(int i=0;i<prime_num;i++)
        if(prime[i]==x)
            return 1;
    return 0;

}
int main()
{
    prime_num=chooseprime();
    int result=0;
    int num;
    cin >> num;
    for(int i=0;i<prime_num && prime[i]<=num;i++)
    {
        int y=prime[i];
        int x=num-y;
        if(is_num(x))
        {
            if(y<=x)
                result++;
        }
    }
    cout << result << endl;
    return 0;
}

运行正常AC，自我练习，非最优解。

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_34039018/article/details/88404570
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-06-28 01:30:35
阅读 ( 1086 )
分类：职场

【练习】腾讯2017秋招笔试编程题——3. 素数对

【练习】腾讯2017秋招笔试编程题——3. 素数对

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看