回 帖 发 新 帖 刷新版面

主题:prime test 素数问题

Time Limit: 5000ms, Special Time Limit:10000ms, Memory Limit:65536KB  
Total submit users: 328, Accepted users: 37  
Problem 10007 : No special judgement  
Problem description 
Given a big integer number, you are required to find out whether it's a prime number.

 
Input 
The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 254).

 
Output 
For each test case, if N is a prime number, output a line containing the word "Prime", otherwise, output a line containing the smallest prime factor of N.

 
Sample Input 
2
5
10
 
Sample Output 
Prime
2
 
Problem Source 
POJ Monthly
 
哪位高手能帮帮菜鸟啊? 谢谢了!

回复列表 (共4个回复)

沙发


#include <iostream> 
#include <math.h> 
#include <iomanip> 
using namespace std; 
int main( ) 
{
    int m,k,i,n=0; 
     bool prime;      //定义布尔变量prime 
 for(m=101;m<=200;m=m+2)     //判别m是否为素数,m由101变化到200,增量为2 
   {
                             prime=true;   //循环开始时设prime为真,即先认为m为素数 
                             k=int(sqrt(m));          //用k代表根号m的整数部分 
                             for(i=2;i<=k;i++)        //此循环作用是将m被2~根号m除,检查是否能整除 
                             if(m%i==0)             //如果能整除,表示m不是素数 
  
                             {
                                                     prime=false;       //使prime变为假 
                                                         break;             //终止执行本循环 
                              } 
                              if (prime)               //如果m为素数 
                              {
                                                       cout<<setw(5)<<m;     //输出素数m,字段宽度为5 
                                                       n=n+1;                //n用来累计输出素数的个数  
                               }
 
  
                            if(n%10==0) cout<<endl;  //输出10个数后换行 
 
  }
  system("pause"); 
 cout<<endl;                  //最后执行一次换行 
 return 0;
 
}

板凳

这是我以前写的 代码
和你的要求有一些不同,
但大致一样,自己修改一下,
…………

3 楼

楼上的肯定不行,大数的素数测试时不能暴力的(最好的暴力是筛法--个人认为)
,只能用米勒测试~~~~~

4 楼

这个不是很难

我来回复

您尚未登录,请登录后再回复。点此登录或注册