编程介的小学生
2019-01-01 00:02
采纳率: 92.7%
浏览 799

2019第一个问题,请问用C语言怎么实现素数的这个算法?

Problem Description
Let d(x) be the sum of all divisors of x. x is called a good number if every number from 1 to d(x) can be expressed as a sum of distinct divisors of x.

For example, 6 is a good number, d(6)=1+2+3+6=12, 4=1+3,5=2+3,7=1+6 and so on.

Teacher Mai wants to know whether a even number p can be expressed as a sum of two good numbers.

Input
There are multiple test cases(about 40000).

For each test case, there is only one line contains one even number p(1≤p≤1018).

Most test cases are generated randomly.

Output
For each test case, print "YES" or "NO" in the first line. That means if is possible to express p as a sum of two good numbers.

If your answer is "YES", print two number a,b in the second lines. Both a and b should be good numbers, and a+b=p.

In the third and the fourth line, print the factorization of number a and b. If a=∏ki=1peii, where p1<p2<⋯<pk, pi are all prime numbers and ei≥1, you should print k first, then 2k space-seperated numbers p1,e1,p2,e2,⋯,pk,ek.

Sample Input
18

Sample Output
YES
6 12
2 2 1 3 1
2 2 2 3 1

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • blownewbee 2019-10-04 08:02
    已采纳
    点赞 打赏 评论
  • 瑾怀轩 2019-01-01 12:46

    bool prime(int n)
    {
    if(n<2)
    return false;
    else
    {
    for(int i=2;i<=sqrt(n);i++)
    {
    if(n%i==0)
    return false;
    }
    }
    return true;
    题目是素数,下边题可不是求素数问题哦

    点赞 打赏 评论

相关推荐 更多相似问题