CodeForces 584D – Dima and Lisa [数论]

点击打开codeforces题目链接

题意

给你一个大于等于3的奇数N,让你把它分成K个素数,k在[1, 3]内,即将N分成不多余3个素数。

分析

昨天做这题光想哥德巴赫猜想这个猜想本身了,没往正解上想….猜想本身是任一大于2的偶数都可写成两个素数之和,任一大于7的奇数都可写成三个质数之和。

看官方题解,思路就是,因为10^9内任意两个素数之间的间隔小于300,然后找到N以内最大的素数P来,剩下的偶数N-P可以分解为两个素数,此时N-P<300,直接暴力出即可。

C++代码

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if(n == 1) return false;
    for(int i = 2; i * i <= n; ++i)
        if(n % i == 0)
            return false;
    return true;
}

int main() {
    int n; scanf("%d", &n);
    if(isPrime(n)) {
        printf("1\n%d\n", n);
        return 0;
    }
    if(isPrime(n-2)) {
        printf("2\n2 %d\n", n-2);
        return 0;
    }
    int i;
    for(i = 2; i < n; i += 2) {
        if(isPrime(n - i))
            break;
    }
    for(int j = 2; j < i; ++j) {
        if(isPrime(j) && isPrime(i - j)) {
            printf("3\n%d %d %d\n", j, i-j, n-i);
            return 0;
        }
    }
    return 0;
}

欢迎留言