Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
Content added Content deleted
(Set the number of results to 20 as required.) |
(New post.) |
||
Line 312: | Line 312: | ||
Most of the time here is the substring testing, so this could be better optimized. |
Most of the time here is the substring testing, so this could be better optimized. |
||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
import java.math.BigInteger; |
|||
import java.util.ArrayList; |
|||
import java.util.Collections; |
|||
import java.util.List; |
|||
import java.util.concurrent.ThreadLocalRandom; |
|||
public final class CompositeNumbersK { |
|||
public static void main(String[] aArgs) { |
|||
int k = 11 * 11; |
|||
List<Integer> result = new ArrayList<Integer>(); |
|||
while ( result.size() < 20 ) { |
|||
while ( k % 3 == 0 || k % 5 == 0 || k % 7 == 0 ) { |
|||
k += 2; |
|||
} |
|||
List<Integer> factors = primeFactors(k); |
|||
if ( factors.size() > 1 ) { |
|||
String stringK = String.valueOf(k); |
|||
if ( factors.stream().allMatch( factor -> stringK.indexOf(String.valueOf(factor)) >= 0 ) ) { |
|||
result.add(k); |
|||
} |
|||
} |
|||
k += 2; |
|||
} |
|||
for ( int i = 0; i < result.size(); i++ ) { |
|||
System.out.print(String.format("%10d%s", result.get(i), ( i == 9 || i == 19 ? "\n" : "" ))); |
|||
} |
|||
} |
|||
private static List<Integer> primeFactors(int aK) { |
|||
ArrayList<Integer> result = new ArrayList<Integer>(); |
|||
if ( aK <= 1 ) { |
|||
return result; |
|||
} |
|||
BigInteger bigK = BigInteger.valueOf(aK); |
|||
if ( bigK.isProbablePrime(CERTAINTY_LEVEL) ) { |
|||
result.add(aK); |
|||
return result; |
|||
} |
|||
int divisor = pollardsRho(bigK).intValueExact(); |
|||
result.addAll(primeFactors(divisor)); |
|||
result.addAll(primeFactors(aK / divisor)); |
|||
Collections.sort(result); |
|||
return result; |
|||
} |
|||
private static BigInteger pollardsRho(BigInteger aN) { |
|||
final BigInteger constant = new BigInteger(aN.bitLength(), RANDOM); |
|||
BigInteger x = new BigInteger(aN.bitLength(), RANDOM); |
|||
BigInteger xx = x; |
|||
BigInteger divisor = null; |
|||
if ( aN.mod(BigInteger.TWO).signum() == 0 ) { |
|||
return BigInteger.TWO; |
|||
} |
|||
do { |
|||
x = x.multiply(x).mod(aN).add(constant).mod(aN); |
|||
xx = xx.multiply(xx).mod(aN).add(constant).mod(aN); |
|||
xx = xx.multiply(xx).mod(aN).add(constant).mod(aN); |
|||
divisor = x.subtract(xx).gcd(aN); |
|||
} while ( divisor.compareTo(BigInteger.ONE) == 0 ); |
|||
return divisor; |
|||
} |
|||
private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current(); |
|||
private static final int CERTAINTY_LEVEL = 10; |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 |
|||
5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |