POJ NOI MATH-7827 质数的和与积

一时失言乱红尘 2022-01-09 10:59 269阅读 0赞

**问题链接**： [POJ NOI MATH-7827 质数的和与积][POJ NOI MATH-7827] 。

总时间限制:

1000ms

内存限制:

65536kB

描述

两个质数的和是S，它们的积最大是多少？

输入

一个不大于10000的正整数S，为两个质数的和。

输出

一个整数，为两个质数的最大乘积。数据保证有解。

样例输入

50

样例输出

589

来源

《奥数典型题举一反三（小学五年级）》 (ISBN 978-7-5445-2882-5) 第三章 第二讲 例1

--------------------

**问题分析**

需要注意特殊的情形，例如输入的S为4。

**程序说明**

程序中，使用埃拉托斯特尼筛选法计算小于10000的素数。

似乎输入的S不为两个素数之和时，需要输出0。

--------------------

AC的C++语言程序：

#include <iostream>
    #include <cmath>
    #include <cstring>
    
    using namespace std;
    
    const int N = 10000;
    
    int prime[N+1];
    
    void esieve(int n)
    {
        memset(prime, 1, sizeof(prime));
        prime[1] = 0;
    
        // 筛选
        int max = sqrt(n);
        for(int i=2; i<=max; i++)
            if(prime[i])
                for(int j=i+i; j <= n; j+=i)
                    prime[j] = 0;
    }
    
    int main()
    {
        int s;
    
        esieve(N);
    
        cin >> s;
    
        if(s & 1)
            if(prime[s- 2])
                cout << 2 * (s - 2) << endl;
            else
                cout << 0 << endl;
        else {
            int i, j;
            i = j = s / 2;
            while(prime[i] == 0 || prime[j] == 0)
                i++, j--;
            cout << i * j << endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/tigerisland/p/7563963.html

[POJ NOI MATH-7827]: http://noi.openjudge.cn/math/7827/

发表评论取消回复

表情：

评论列表（有 0 条评论，269人围观）

还没有评论，来说两句吧...

相关阅读

相关质数的和与积

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6LaFMzM4_size_20_color_FFFFFF_t_7

女爷i/ 2023年09月29日 10:39/ 0 赞/ 12 阅读

相关 Poj 2318 TOYS (叉积+二分)

好久没做计算几何了，随便找道题恢复下手感，明显感觉写复杂了。。。。应该是最后一道用vc6.0敲的题了，下一道改用codeblocks 题意：给定一个长方形箱子，中间有n条

青旅半醒/ 2023年01月17日 06:21/ 0 赞/ 162 阅读

相关质数中的质数

质数中的质数 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述如果一个质数，它在质数

系统管理员/ 2022年08月14日 05:50/ 0 赞/ 185 阅读

相关 100以内的质数及100以内质数的和

public static void main(String[] args) { //--------------质数：除了1和它本身之外不能被整除的数--

叁歲伎倆/ 2022年08月06日 00:24/ 0 赞/ 227 阅读

相关质数中的质数（质数筛法

如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数

迈不过友情╰/ 2022年06月11日 05:44/ 0 赞/ 199 阅读

相关 HDU 5628 Clarke and math （Dirichlet卷积）

题目链接： [HDU 5628][] 题意：给你f(i)。(i=1,2,…,n) 求g(i)=∑i1∣i∑i2∣i1∑i3∣i2⋯∑ik∣ik−1f(ik) m

骑猪看日落/ 2022年06月09日 10:13/ 0 赞/ 183 阅读

相关 POJ 2398(计算几何叉积)

[题目链接][Link 1] 题目大意：给你一个被n块挡板分隔成n+1个区域的盒子，给你m个点，从小到大输出含有点的个数的区域有多少个分析：这题其实和POJ 2318差不

落日映苍穹つ/ 2022年05月18日 02:39/ 0 赞/ 216 阅读

相关 POJ 2318 (计算几何叉积)

[题目链接][Link 1] 题意：给你一个被n块挡板分隔成n+1个区域的盒子，给你m个点，问你每个区域有多少个点。分析：这道题其实就是考对叉积的应用，计算矢量叉积是与直

小灰灰/ 2022年05月18日 02:37/ 0 赞/ 188 阅读

相关小学奥数：质数的和与积

描述两个质数的和是S，它们的积最大是多少？输入一个不大于10000的正整数S，为两个质数的和。输出一个整数，为两个质数的最大乘积。数据保证有解。样例输入

﹏ヽ暗。殇╰゛Y/ 2022年03月30日 05:54/ 0 赞/ 467 阅读

相关 POJ NOI MATH-7827 质数的和与积

问题链接： [POJ NOI MATH-7827 质数的和与积][POJ NOI MATH-7827] 。总时间限制: 1000ms 内存限制:

一时失言乱红尘/ 2022年01月09日 10:59/ 0 赞/ 270 阅读