首页 > 代码库 > UVa 10490 - Mr. Azad and his Son!!!!!
UVa 10490 - Mr. Azad and his Son!!!!!
题目:给你一个数k判断2^(k-1)*(2^k-1)是不是完全数(真因数之和和自身相等),不是判断k是不是素数。
分析:数论。欧拉证明了所有偶完全数都满足式子2^(k-1)*(2^k-1);其中2^k-1为素数时,上式为完全数。
满足2^k-1形式的素数叫梅森素数,这里打表计算50000内的素数判断2^k-1是不是素数即可。
(如果存在,超过50000的素数因子只能有一个,而且一定是素数)
说明:又见数论(⊙o⊙)。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int visit[50000]; int prime[50000]; int perfect[32]; int main() { memset(visit, 0, sizeof(visit)); visit[0] = visit[1] = 1; int count = 0; for (int i = 2 ; i < 50000 ; ++ i) if (!visit[i]) { prime[count ++] = i; for (int j = i+i ; j < 50000 ; j += i) visit[j] = 1; } memset(perfect, 0, sizeof(perfect)); for (int i = 2 ; i < 32 ; ++ i) { int V = (1<<i)-1,flag = 0; for (int j = 0 ; j < count ; ++ j) while (V%prime[j] == 0) { V /= prime[j]; flag ++; } if (V != 1) flag ++; if (flag == 1) perfect[i] = 1; } int n; while (scanf("%d",&n) && n) if (perfect[n]) printf("Perfect: %lld!\n",(1LL<<(n-1LL))*((1LL<<n)-1LL)); else if (!visit[n]) printf("Given number is prime. But, NO perfect number is available.\n"); else printf("Given number is NOT prime! NO perfect number is available.\n"); return 0; }
UVa 10490 - Mr. Azad and his Son!!!!!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。