fork(1) download
copy 
  1. /* programming with prime numbers */
  2.  
  3. import java.util.LinkedList;
  4. import java.util.BitSet;
  5. import java.math.BigInteger;
  6. import java.lang.Exception;
  7. import java.lang.Boolean;
  8. import java.util.Random;
  9. import java.util.Collections;
  10.  
  11. class Main {
  12.  
  13.     public static LinkedList primes(int n)
  14.     {
  15.         if (n < 2)
  16.         {
  17.             throw new IllegalArgumentException("must be greater than one");
  18.         }
  19.  
  20.         int m = (n-1) / 2;
  21.         BitSet b = new BitSet(m);
  22.         b.set(0, b.size(), true);
  23.  
  24.         int i = 0;
  25.         int p = 3;
  26.         LinkedList ps = new LinkedList();
  27.         ps.add(2);
  28.  
  29.         while (p * p < n)
  30.         {
  31.         if (b.get(i))
  32.             {
  33.                 ps.add(p);
  34.                 int j = 2*i*i + 6*i + 3;
  35.                 while (j < m)
  36.                 {
  37.                     b.clear(j);
  38.                     j = j + 2*i + 3;
  39.                 }
  40.             }
  41.             i += 1; p += 2;
  42.         }
  43.  
  44.         while (i < m)
  45.         {
  46.             if (b.get(i))
  47.             {
  48.                 ps.add(p);
  49.             }
  50.             i += 1; p += 2;
  51.         }
  52.  
  53.         return ps;
  54.     }
  55.  
  56.     public static Boolean tdPrime(BigInteger n)
  57.     {
  58.         BigInteger two = BigInteger.valueOf(2);
  59.  
  60.         if (n.compareTo(two) < 0)
  61.         {
  62.             throw new IllegalArgumentException("must be greater than one");
  63.         }
  64.  
  65.         if (n.mod(two).equals(BigInteger.ZERO))
  66.         {
  67.             return n.equals(two);
  68.         }
  69.  
  70.         BigInteger d = BigInteger.valueOf(3);
  71.  
  72.         while (d.multiply(d).compareTo(n) <= 0)
  73.         {
  74.             if (n.mod(d).equals(BigInteger.ZERO))
  75.             {
  76.                 return false;
  77.             }
  78.             d = d.add(two);
  79.         }
  80.  
  81.         return true;
  82.     }
  83.  
  84.     public static LinkedList tdFactors(BigInteger n)
  85.     {
  86.         BigInteger two = BigInteger.valueOf(2);
  87.         LinkedList fs = new LinkedList();
  88.  
  89.         if (n.compareTo(two) < 0)
  90.         {
  91.             throw new IllegalArgumentException("must be greater than one");
  92.         }
  93.  
  94.         while (n.mod(two).equals(BigInteger.ZERO))
  95.         {
  96.             fs.add(two);
  97.             n = n.divide(two);
  98.         }
  99.  
  100.         if (n.compareTo(BigInteger.ONE) > 0)
  101.         {
  102.             BigInteger f = BigInteger.valueOf(3);
  103.             while (f.multiply(f).compareTo(n) <= 0)
  104.             {
  105.                 if (n.mod(f).equals(BigInteger.ZERO))
  106.                 {
  107.                     fs.add(f);
  108.                     n = n.divide(f);
  109.                 }
  110.                 else
  111.                 {
  112.                     f = f.add(two);
  113.                 }
  114.             }
  115.             fs.add(n);
  116.         }
  117.  
  118.         return fs;
  119.     }
  120.  
  121.     private static Boolean isSpsp(BigInteger n, BigInteger a)
  122.     {
  123.         BigInteger two = BigInteger.valueOf(2);
  124.         BigInteger n1 = n.subtract(BigInteger.ONE);
  125.         BigInteger d = n1;
  126.         int s = 0;
  127.  
  128.         while (d.mod(two).equals(BigInteger.ZERO))
  129.         {
  130.             d = d.divide(two);
  131.             s += 1;
  132.         }
  133.  
  134.         BigInteger t = a.modPow(d, n);
  135.  
  136.         if (t.equals(BigInteger.ONE) || t.equals(n1))
  137.         {
  138.             return true;
  139.         }
  140.  
  141.         while (--s > 0)
  142.         {
  143.             t = t.multiply(t).mod(n);
  144.             if (t.equals(n1))
  145.             {
  146.                 return true;
  147.             }
  148.         }
  149.  
  150.         return false;
  151.     }
  152.  
  153.     public static Boolean isPrime(BigInteger n)
  154.     {
  155.         Random r = new Random();
  156.         BigInteger two = BigInteger.valueOf(2);
  157.         BigInteger n3 = n.subtract(BigInteger.valueOf(3));
  158.         BigInteger a;
  159.         int k = 25;
  160.  
  161.         if (n.compareTo(two) < 0)
  162.         {
  163.             return false;
  164.         }
  165.  
  166.         if (n.mod(two).equals(BigInteger.ZERO))
  167.         {
  168.             return n.equals(two);
  169.         }
  170.  
  171.         while (k > 0)
  172.         {
  173.             a = new BigInteger(n.bitLength(), r).add(two);
  174.             while (a.compareTo(n) >= 0)
  175.             {
  176.                 a = new BigInteger(n.bitLength(), r).add(two);
  177.             }
  178.  
  179.             if (! isSpsp(n, a))
  180.             {
  181.                 return false;
  182.             }
  183.  
  184.             k -= 1;
  185.         }
  186.  
  187.         return true;
  188.     }
  189.  
  190.     private static BigInteger rhoFactor(BigInteger n, BigInteger c)
  191.     {
  192.         BigInteger t = BigInteger.valueOf(2);
  193.         BigInteger h = BigInteger.valueOf(2);
  194.         BigInteger d = BigInteger.ONE;
  195.  
  196.         while (d.equals(BigInteger.ONE))
  197.         {
  198.             t = t.multiply(t).add(c).mod(n);
  199.             h = h.multiply(h).add(c).mod(n);
  200.             h = h.multiply(h).add(c).mod(n);
  201.             d = t.subtract(h).gcd(n);
  202.         }
  203.  
  204.         if (d.equals(n)) /* cycle */
  205.         {
  206.             return rhoFactor(n, c.add(BigInteger.ONE));
  207.         }
  208.         else if (isPrime(d)) /* success */
  209.         {
  210.             return d;
  211.         }
  212.         else /* found composite factor */
  213.         {
  214.             return rhoFactor(d, c.add(BigInteger.ONE));
  215.         }
  216.     }
  217.  
  218.     public static LinkedList rhoFactors(BigInteger n)
  219.     {
  220.         BigInteger f;
  221.         BigInteger two = BigInteger.valueOf(2);
  222.         LinkedList fs = new LinkedList();
  223.  
  224.         if (n.compareTo(two) < 0)
  225.         {
  226.             return fs;
  227.         }
  228.  
  229.         while (n.mod(two).equals(BigInteger.ZERO))
  230.         {
  231.             n = n.divide(two);
  232.             fs.add(two);
  233.         }
  234.  
  235.         if (n.equals(BigInteger.ONE))
  236.         {
  237.             return fs;
  238.         }
  239.  
  240.         while (! n.isProbablePrime(25))
  241.         {
  242.             f = rhoFactor(n, BigInteger.ONE);
  243.             n = n.divide(f);
  244.             fs.add(f);
  245.         }
  246.  
  247.         fs.add(n);
  248.         Collections.sort(fs);
  249.         return fs;
  250.     }
  251.  
  252.     public static void main (String[] args)
  253.     { 
  254.         System.out.println(primes(100));
  255.         System.out.println(primes(1000000).size());
  256.         System.out.println(tdPrime(new BigInteger("600851475143")));
  257.         System.out.println(tdFactors(new BigInteger("600851475143")));
  258.         System.out.println(isPrime(new BigInteger("600851475143")));
  259.         System.out.println(isPrime(new BigInteger("2305843009213693951")));
  260.         System.out.println(rhoFactors(new BigInteger("600851475143")));
  261.     }
  262.  
  263. }
Success #stdin #stdout 0.11s 246080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
78498
false
[71, 839, 1471, 6857]
false
true
[71, 839, 1471, 6857]
https://ideone.com/jHVJd
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
secret

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!