OJ Board

Posted: **Sat May 07, 2005 10:06 am**

How to find the the smallest prime factor of N? Who can help me?

Prime Test

Time Limit:10000MS Memory Limit:10000K

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 < 2^54).
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

Posted: **Sat May 07, 2005 3:59 pm**

2^54 is not so big!
The following function solves the problem.

Code: Select all

function get_smallest_factor(n: int64): int64;
 var
   i: integer;
   sq1, sq2: int64;
begin
  result:= 0;
  sq2:= n div 2;
  repeat
    sq1:= sq2;
    sq2:= (sq1+n div sq1) div 2;
  until sq2=sq1;
  for i:=2 to sq2+1 do
    if n mod i = 0 then begin
      result:= i;
      exit;
    end; 
end;

It returns 0 if n is prime and smallest factor otherwise.

Edited:
This function worked about minute on my old
computer on the biggest prime number less then 2^54
N = 2^54-33 = 18014398509481951
So maybe you really should use some probabilistic
methods which are widely covered in Knuth.

Posted: **Sat May 07, 2005 4:30 pm**

If you want a fast solution, you can try some probabilistic algorithm, read the following sites:
http://mathworld.wolfram.com/PrimalityTest.html
http://mathworld.wolfram.com/PollardRho ... ethod.html

OJ Board

SOS , tell me the algorithm , thanks

SOS , tell me the algorithm , thanks