题目链接:UVA10006

本来想直接打素数表,然后根据素数表来判断,结果一直超时,后来把素数表去掉,再在for循环中加判断才勉强过了。

Some numbers that are not prime still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers.

只要按着这两个条件判断即可。

具体看代码:

#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
bool isPrimer(int num);
int powerMode(int,int,int);
//bool primeTable[65010];
int main()
{
// for(int i=1;i<=65010;i++)
// if(isPrimer(i))
// primeTable[i]=1; //素数标为1
// else
// primeTable[i]=0;
int number;
while(cin>>number,number!=0)
{
bool flag=0;
// not prime
if(isPrimer(number))
flag=1;
// pass the Fermat test with every
// number smaller than themselves.
//Let a be a random number between 2 and n - 1
for(int i=2;(i<number)&&!flag;i++)
if(powerMode(i,number,number)!=i)
flag=1; if(flag)
cout<<number<<" is normal."<<endl;
else
cout<<"The number "<<number<<" is a Carmichael number."<<endl;
}
return 0;
}
bool isPrimer(int number)
{
if(number<=2)
return true;
if(number%2==0)
return false;
for(int i=3;i<=ceil(sqrt(number));i++)
if(number%i==0)
return false;
return true;
}
//计算 pow(a,n)%n=a
int powerMode(int a,int n,int mode)
{
long long answer=1;
while(n)
{
if(n&1)
answer=(answer*a)%mode;
a=((long long )a*a)%mode;
n=n>>1;
}
return answer;
}

最新文章

  1. lua中清空目录和递归创建目录
  2. erlang服务器启动,有情况会报,enif_send: env==NULL no ono-SMP VMAborted 的错误报告?
  3. ROW_NUMBER()函数的使用
  4. iOS10适配及Xcode8配置
  5. Codeforces Round #367 (Div. 2) B. Interesting drink (模拟)
  6. Java视频教程
  7. 你好,C++(12)怎样管理多个类型同样性质同样的数据?3.6 数组
  8. JavaScript对css样式表操作
  9. BCM wifi驱动学习
  10. php编码
  11. CentOS 6.4 文件夹打开方式
  12. MyBatis CRUD Java POJO操作
  13. POJ 3683 Priest John&#39;s Busiest Day / OpenJ_Bailian 3788 Priest John&#39;s Busiest Day(2-sat问题)
  14. KVO键值观察的具体实现
  15. linux apache虚拟主机配置(基于ip,端口,域名)
  16. 构建基于Netty 的HTTP/HTTPS 应用程序
  17. 解决MyEclipse启动慢,使用卡顿问题
  18. Base64编码解码JS
  19. Fence Repair POJ - 3253 哈夫曼思想 优先队列
  20. ACM-ICPC 2018 焦作赛区网络预赛 J Participate in E-sports(大数开方)

热门文章

  1. iOS点击状态栏回到顶部底层实现原理
  2. CMS系统的实现图
  3. 关于工程结合git的配置
  4. 【bzoj2118】 墨墨的等式
  5. ListView介绍
  6. CSS从大图片上截取小图标的操作
  7. Android 学习笔记之AndBase框架学习(二) 使用封装好的进度框,Toast框,弹出框,确认框...
  8. python学习-day01
  9. [SQL] cast 与 convert 都在什么情况下使用
  10. Java学习笔记之:Java 流
  11. usb.ids
  12. centos防火墙操作
  13. VirtualBox 扩展包卸载或安装失败(VERR_ALREADY_EXISTS)
  14. 依赖注入及AOP简述(十一)——生命周期管理 .
  15. poj 3100
  16. CreateFile函数使用方法详细介绍
  17. uploadify 配置后,页面显示无效果
  18. Ubuntu下teamviewer的安装
  19. Python多版本管理器-pyenv 介绍及部署记录
  20. LOJ10067 构造完全图