fork(20) download
copy 
  1. import java.math.BigInteger;
  2. import java.security.SecureRandom;
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. public class PollardRho {
  7.  
  8.     private final static BigInteger ZERO = new BigInteger("0");
  9.     private final static BigInteger ONE  = new BigInteger("1");
  10.     private final static BigInteger TWO  = new BigInteger("2");
  11.     private final static SecureRandom random = new SecureRandom();
  12.  
  13.     static Vector<BigInteger> v = new Vector<BigInteger>();
  14.     static HashMap<Long,Long> m = new HashMap();
  15.     public static BigInteger rho(BigInteger N) {
  16.  
  17.         BigInteger divisor;
  18.         BigInteger c  = new BigInteger(N.bitLength(), random);
  19.         BigInteger x  = new BigInteger(N.bitLength(), random);
  20.         BigInteger xx = x;
  21.  
  22.         if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;
  23.  
  24.         do {
  25.             x  =  x.multiply(x).mod(N).add(c).mod(N);
  26.             xx = xx.multiply(xx).mod(N).add(c).mod(N);
  27.             xx = xx.multiply(xx).mod(N).add(c).mod(N);
  28.             divisor = x.subtract(xx).gcd(N);
  29.         } while((divisor.compareTo(ONE)) == 0);
  30.  
  31.         return divisor;
  32.     }
  33.  
  34.     public static void factor(BigInteger N) {
  35.  
  36.         if (N.compareTo(ONE) == 0) return;
  37.  
  38.         if (N.isProbablePrime(20)) {
  39.             v.add(N);
  40.             return;
  41.         }
  42.  
  43.         BigInteger divisor = rho(N);
  44.         factor(divisor);
  45.         factor(N.divide(divisor));
  46.     }
  47.  
  48.     public static void main(String[] args) throws Exception {
  49.  
  50.        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  51. long num = Long.parseLong(br.readLine());
  52.         BigInteger N = new BigInteger(num+"");
  53.         factor(N);
  54.  
  55.        int sz = v.size();
  56.        Collections.sort(v);
  57.        long cnt = 0;
  58.        long tot = 1;
  59.        for(int i=0;i<sz;i++){
  60.  
  61.     	   cnt = 0;
  62.     	   while(i+1<sz&&v.get(i).equals(v.get(i+1))){
  63.  
  64.     		   cnt++; i++;
  65.     	   }
  66.     	   cnt++;
  67.     	   tot *= (cnt+1);
  68.        }
  69.         System.out.println(tot);
  70.  
  71.  
  72.     }
  73. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:6: error: class PollardRho is public, should be declared in a file named PollardRho.java
public class PollardRho {
       ^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
stdout
copy 
Standard output is empty
https://ideone.com/3dnYAv
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!