首页 > 专题系列 > Java解POJ > POJ 1811 Prime Test [解题报告] Java
2013
11-10

POJ 1811 Prime Test [解题报告] Java

Prime Test

问题描述 :

Given a big integer number, you are required to find out whether it’s a prime number.

输入:

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).

输出:

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.

样例输入:

2
5
10

样例输出:

Prime
2

解题代码:

/* @author: */
//给定一个数N,判断数N是否为素数,如果是素数则输出"Prime",否则输出数N的最小素因子

import java.util.Random;
import java.util.Scanner;
//http://en.wikipedia.org/wiki/Pollard's_rho_algorithm
public class Main{
   static int MAX_COUNT = 6;
   static long allFactor[ ]=new long [65];
   static int nFactor;
   static Random rn=new Random();
	
 static long  fMultiModular(   long a,   long b,   long  n)
{
  long back = 0, temp = a % n;
  while ( b > 0 )
  {
     if ( (b & 0x1)==1 )
     {
        if ( (back = back + temp) > n )
          back -= n;
      }//modres=back
      if ( (temp <<= 1) > n )
	 temp -= n;//temp=a^(xx)

	b >>= 1;
  }
  return back;
 }

 static long   GCD(long    a , long  b)
{
  int z = 0;
  while(b != 0 && a != 0)
  {
   while((a & 1) == 0 && (b & 1) == 0)
   {
	z++;
	a >>= 1;
	b >>= 1;
   }
  while((a & 1) == 0)
  {
	a >>= 1;
  }
  while((b & 1) == 0)
  {
	b >>= 1;
  }
 if(a > b)
 {
	a -= b;
 }
 else
 {
	b -= a;
 }
}//while
if(b == 0)
{
 return a << z;
}
 return b << z;
}


static long modular_exp( long  a, long b, long n)
{
	long d=1, dTemp=(a % n);
    while ( b > 0 )
    {
        if ( (b & 0x1)==1 )
            d = fMultiModular(d, dTemp, n);
        dTemp = fMultiModular(dTemp, dTemp, n);
        b >>= 1;
    }
    return d;
}

static boolean fWitNess(long  a, long  n, int t, long  u)
{
	long x, y = 0;
 x = modular_exp(a, u, n);
 while ( t-- >0)
 {
  y = fMultiModular(x, x, n);
  if ( y == 1 && x != 1 && x != n-1 )
   return true; //must not
  x = y;
 }
 return y != 1;
}


static boolean  miller_rabin(long n, int count) 
{
    if ( n == 1 )
        return false;
    if ( n == 2 )
	return true;
 
  long  a, u;    
    int t=0; 
    for (u = n-1; !((u & 0x1)==1); u>>=1)
  ++t;//2's power
    for (int i = 1; i <= count; ++i)
    {
        a = rand() % (n-1) + 1;
        if ( fWitNess(a, n, t, u) )
		 return false;
    }
    return true;
}

static long  pollard_rho(long c, long num)
{
    int i=(1), k=(2);
   long x = rand() % num;
   long y = x, comDiv;
    do
    {
        ++i;
        if ( (x = fMultiModular(x, x, num) - c) < 0 )
   x += num;
        if ( x == y )
            break;
        comDiv = GCD((y-x+num)%num, num);
        if ( comDiv > 1 && comDiv < num )
            return comDiv;
        if ( i == k )
        {
            y = x;
            k <<= 1;
        }
    }while ( true );
    return num;
}

static void fFindFactor(long num)
{
    if ( miller_rabin(num, MAX_COUNT) == true )
    {
    allFactor[++nFactor] = num; 
 // printf("%I64d ",num);
        return;
    }
    long factor;
    do
    {
        factor = pollard_rho(rand()%(num-1) + 1, num);
    }while ( factor >= num );

    fFindFactor(factor);
    fFindFactor(num/factor);
}

 static long rand()
 {
	 long temp=rn.nextLong();
	 if(temp< 0)
		 temp+=Long.MAX_VALUE;
	 return 
	temp;
 }

 public static void main(String args[])
 {
	int t, i;
	Scanner cin = new Scanner(System.in);
	long test_num, min;
	t = cin.nextInt();
	while (t-- > 0) {
         test_num = cin.nextLong();
	  //BigInteger testprime = new BigInteger(Long.toString(test_num));
	  // if(testprime.isProbablePrime(20))
	  if (miller_rabin(test_num, 20))				
		System.out.println("Prime");
	  else {
           min = test_num;
	    nFactor = 0;
	    fFindFactor(test_num);
	    for (i = 1; i <= nFactor; i++) {
		if (allFactor[i] < min)
		  min = allFactor[i];
	    }
	    System.out.println(min);
	 }
     }
  }
}

  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }