Download code

Jump to: navigation, search

Back to Trial_division_(Java)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

TrialDivision.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Trial_division_(Java)?oldid=19223
 14 */
 15 
 16 import java.util.BitSet;
 17 
 18 class TrialDivision {
 19 
 20     public static final int IS_PRIME = 0;
 21 
 22     public static int trialDivisionSqrt(int n) {
 23         int sqrtN = (int)Math.sqrt((double)n);
 24         for (int x = 2; x <= sqrtN; x++) {
 25             if (n % x == 0) {
 26                 return x;
 27             }
 28         }
 29         return IS_PRIME;
 30     }
 31 
 32 
 33     static int trialDivisionSquaring(int n) {
 34         for (int x = 2, xSquared = 4;
 35             xSquared > 2*x - 1 && xSquared <= n;
 36             x++, xSquared += 2*x - 1)
 37         {
 38             if (n % x == 0) {
 39                 return x;
 40             }
 41         }
 42         return IS_PRIME;
 43     }
 44 
 45     public static int trialDivisionOdd(int n) {
 46         int sqrtN = (int)Math.sqrt((double)n);
 47         if (n % 2 == 0) return 2;
 48         for (int x = 3; x <= sqrtN; x += 2) {
 49             if ((n % x) == 0) {
 50                 return x;
 51             }
 52         }
 53         return IS_PRIME;
 54     }
 55 
 56     static int[] primes;
 57 
 58     static private void generatePrimeList(int max) {
 59         BitSet isNotPrime = new BitSet(max+1);
 60         int numPrimes = 1;
 61         for (int i = 2; i <= max; i++) {
 62             if (!isNotPrime.get(i)) {
 63                 numPrimes++;
 64                 for (int j = i + i; j <= max; j += i) {
 65                     isNotPrime.set(j);
 66                 }
 67             }
 68         }
 69         primes = new int[numPrimes];
 70         int j = 0;
 71         for (int i = 2; i <= max; i++) {
 72             if (!isNotPrime.get(i)) {
 73                 primes[j] = i;
 74                 j++;
 75             }
 76         }
 77     }
 78 
 79 
 80     public static int trialDivisionPrimes(int n) {
 81         int sqrtN = (int)Math.sqrt((double)n);
 82         for (int primeIdx = 0; primeIdx < primes.length && primes[primeIdx] <= sqrtN; primeIdx++) {
 83             if (n % primes[primeIdx] == 0) {
 84                 return primes[primeIdx];
 85             }
 86         }
 87         return IS_PRIME;
 88     }
 89 
 90     public static long sqrt(long n) {
 91         long guess = 2, prev_guess = 0, prev2_guess = 0;
 92         while (guess != prev_guess && guess != prev2_guess) {
 93             prev2_guess = prev_guess;
 94             prev_guess = guess;
 95             guess = (guess + n/guess)/2;
 96         }
 97         return Math.min(guess, prev_guess);
 98     }
 99 
100     public static int trialDivisionPrimesLong(long n) {
101         long maxPrime = primes[primes.length-1];
102 	if (maxPrime*maxPrime > n) {
103 	    throw new IllegalArgumentException("Cannot factor numbers larger than " + maxPrime*maxPrime);
104 	}
105         long sqrtN = sqrt(n);
106         for (int primeIdx = 0; primeIdx < primes.length && primes[primeIdx] <= sqrtN; primeIdx++) {
107             if (n % primes[primeIdx] == 0) {
108                 return primes[primeIdx];
109             }
110             
111         }
112         return IS_PRIME;
113     }
114 
115     public static void main(String[] args) {
116         long n = Long.parseLong(args[1]);
117         if (n <= 0) {
118             System.out.println("Please enter only positive integers.");
119         } else if (args[0].equals("TrialDivisionSqrt")) {
120             for (int i = 0; i < 10000 - 1; i++) trialDivisionSqrt((int)n);
121             System.out.println(trialDivisionSqrt((int)n));
122         } else if (args[0].equals("TrialDivisionSquaring")) {
123             for (int i = 0; i < 10000 - 1; i++) trialDivisionSquaring((int)n);
124             System.out.println(trialDivisionSquaring((int)n));
125         } else if (args[0].equals("TrialDivisionOdd")) {
126             for (int i = 0; i < 10000 - 1; i++) trialDivisionOdd((int)n);
127             System.out.println(trialDivisionOdd((int)n));
128         } else if (args[0].equals("TrialDivisionPrimes")) {
129             generatePrimeList(65536);
130             for (int i = 0; i < 10000 - 1; i++) trialDivisionPrimes((int)n);
131             System.out.println(trialDivisionPrimes((int)n));
132         } else if (args[0].equals("TrialDivisionPrimesLong")) {
133             generatePrimeList(Integer.MAX_VALUE/2);
134             for (int i = 0; i < 10000 - 1; i++) trialDivisionPrimesLong(n);
135             System.out.println(trialDivisionPrimesLong(n));
136         } else {
137             System.out.println("Invalid algorithm selection.");
138         }
139     }
140 
141 }


hijacker
hijacker
hijacker
hijacker