Blum integer: Difference between revisions

Content added Content deleted
(→‎{{header|RPL}}: comment on the FACTORS command)
m (Code using an iImproved algorithm.)
Line 401: Line 401:
=={{header|Java}}==
=={{header|Java}}==
<syntaxhighlight lang="java">
<syntaxhighlight lang="java">

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map;


Line 410: Line 408:


public static void main(String[] aArgs) {
public static void main(String[] aArgs) {
final int limit = 10_000_000;
List<Integer> primeNumbersType3 = primeNumbersType3(limit);
int[] leastPrimeFactors = leastPrimeFactors(limit);
int[] blums = new int[50];
int[] blums = new int[50];
int blumCount = 0;
int blumCount = 0;
Line 420: Line 414:
while ( blumCount < 400_000 ) {
while ( blumCount < 400_000 ) {
final int prime = leastPrimeFactors[number];
final int prime = leastPrimeFactor(number);
if ( ( prime & 3 ) == 3 ) {
if ( prime % 4 == 3 ) {
final int quotient = number / prime;
final int quotient = number / prime;
if ( quotient != prime && primeNumbersType3.contains(quotient) ) {
if ( quotient != prime && isPrimeType3(quotient) ) {
if ( blumCount < 50 ) {
if ( blumCount < 50 ) {
blums[blumCount] = number;
blums[blumCount] = number;
Line 450: Line 444:
}
}
}
}
number = ( number % 5 == 3 ) ? number + 4 : number + 2;
number += ( number % 5 == 3 ) ? 4 : 2;
}
}
⚫
}
⚫
private static int[] leastPrimeFactors(int aLimit) {
int[] result = new int[aLimit + 1];
⚫
for ( int i = 2; i * i <= aLimit; i++ ) {
if ( result[i] == 0 ) {
⚫
for ( int k = i * i; k <= aLimit; k += i ) {
if ( result[k] == 0 ) {
result[k] = i;
}
}
}
}
for ( int i = 1; i <= aLimit; i++ ) {
⚫
if ( result[i] == 0 ) {
result[i] = i;
}
}
⚫
return result;
}
}
private static List<Integer> primeNumbersType3(int aLimit) {
private static boolean isPrimeType3(int aNumber) {
if ( aNumber < 2 ) { return false; }
BitSet sieve = new BitSet(aLimit + 1);
⚫
if ( aNumber % 2 == 0 ) { return false; }
sieve.set(2, aLimit + 1);
if ( aNumber % 3 == 0 ) { return aNumber == 3; }
for ( int i = 2; i <= (int) Math.sqrt(aLimit); i = sieve.nextSetBit(i + 1) ) {

for ( int j = i * i; j <= aLimit; j = j + i ) {
⚫
for ( int divisor = 5; divisor * divisor <= aNumber; divisor += 2 ) {
sieve.clear(j);
if ( aNumber % divisor == 0 ) { return false; }
}
}
List<Integer> primesType3 = new ArrayList<Integer>();
for ( int i = 2; i >= 0; i = sieve.nextSetBit(i + 1) ) {
⚫
if ( i % 4 == 3 ) {
primesType3.add(i);
}
}
}
return primesType3;
return aNumber % 4 == 3;
}
}

⚫
private static int leastPrimeFactor(int aNumber) {
⚫
if ( aNumber == 1 ) { return 1; }
if ( aNumber % 3 == 0 ) { return 3; }
if ( aNumber % 5 == 0 ) { return 5; }
⚫
for ( int divisor = 7; divisor * divisor <= aNumber; divisor += 2 ) {
if ( aNumber % divisor == 0 ) { return divisor; }
}
⚫
return aNumber;
⚫
}


}
}
Retrieved from "https://rosettacode.org/wiki/Blum_integer"