2013
11-10

# 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;
}