Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
Composite numbers k with no single digit factors whose factors are all substrings of k (view source)
Revision as of 23:38, 23 February 2024
, 2 months agoAdded FreeBASIC
(Created Nim solution.) |
(Added FreeBASIC) |
||
| (20 intermediate revisions by 10 users not shown) | |||
Line 109:
2237411
3129361</pre>
=={{header|C}}==
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdbool.h>
bool is_substring(unsigned n, unsigned k) {
unsigned startMatch = 0;
for (unsigned pfx = k; n > 0; n /= 10) {
if (pfx % 10 == n % 10) {
pfx /= 10;
if (startMatch == 0) startMatch = n;
} else {
pfx = k;
if (startMatch != 0) n = startMatch;
startMatch = 0;
}
if (pfx == 0) return true;
}
return false;
}
bool factors_are_substrings(unsigned n) {
if (n%2==0 || n%3==0 || n%5==0 || n%7==0) return false;
unsigned factor_count = 0;
for (unsigned factor = 11, n_rest = n; factor <= n_rest; factor += 2) {
if (n_rest % factor != 0) continue;
while (n_rest % factor == 0) n_rest /= factor;
if (!is_substring(n, factor)) return false;
factor_count++;
}
return factor_count > 1;
}
int main(void) {
unsigned amount = 10;
for (unsigned n = 11; amount > 0; n += 2) {
if (factors_are_substrings(n)) {
printf("%u\n", n);
amount--;
}
}
return 0;
}</syntaxhighlight>
{{out}}
<pre>15317
59177
83731
119911
183347
192413
1819231
2111317
2237411
3129361</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
std::vector<uint32_t> primes;
void sieve_primes(const uint32_t& limit) {
std::vector<bool> marked_prime(limit + 1, true);
for ( uint32_t p = 2; p * p <= limit; ++p ) {
if ( marked_prime[p] ) {
for ( uint32_t i = p * p; i <= limit; i += p ) {
marked_prime[i] = false;
}
}
}
for ( uint32_t p = 2; p <= limit; ++p ) {
if ( marked_prime[p] ) {
primes.emplace_back(p);
}
}
}
bool is_substring(const uint32_t& k, const uint32_t& factor) {
const std::string string_k = std::to_string(k);
const std::string string_factor = std::to_string(factor);
return string_k.find(string_factor) != std::string::npos;
}
int main() {
sieve_primes(30'000'000);
std::unordered_set<uint32_t> distinct_factors;
std::vector<uint32_t> result;
uint32_t k = 11 * 11;
while ( result.size() < 10 ) {
while ( k % 3 == 0 || k % 5 == 0 || k % 7 == 0 ) {
k += 2;
}
distinct_factors.clear();
uint32_t copy_k = k;
uint32_t index = 4;
while ( copy_k > 1 ) {
while ( copy_k % primes[index] == 0 ) {
distinct_factors.insert(primes[index]);
copy_k /= primes[index];
}
index += 1;
}
if ( distinct_factors.size() > 1 ) {
if ( std::all_of(distinct_factors.begin(), distinct_factors.end(),
[&k](uint32_t factor) { return is_substring(k, factor); }) ) {
result.emplace_back(k);
}
}
k += 2;
}
for ( uint64_t i = 0; i < result.size(); ++i ) {
std::cout << result[i] << " ";
}
std::cout << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361
</pre>
=={{header|Delphi}}==
Line 203 ⟶ 340:
Elapsed Time: 02:39.291 min
</pre>
=={{header|EasyLang}}==
{{trans|C}} (optimized)
<syntaxhighlight>
fastfunc isin n k .
h = k
while n > 0
if h mod 10 = n mod 10
h = h div 10
if match = 0
match = n
.
else
h = k
if match <> 0
n = match
.
match = 0
.
if h = 0
return 1
.
n = n div 10
.
return 0
.
fastfunc test n .
if n mod 2 = 0 or n mod 3 = 0 or n mod 5 = 0 or n mod 7 = 0
return 0
.
rest = n
fact = 11
while fact <= rest
if rest mod fact = 0
while rest mod fact = 0
rest /= fact
.
if isin n fact = 0
return 0
.
nfacts += 1
.
fact += 2
if fact > sqrt n and nfacts = 0
return 0
.
.
if nfacts > 1
return 1
.
return 0
.
n = 11
while count < 10
if test n = 1
print n
count += 1
.
n += 2
.
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
Line 237 ⟶ 436:
Real: 00:00:26.059
</pre>
=={{header|FreeBASIC}}==
{{trans|ALGOL 68}}
<syntaxhighlight lang="vbnet">Function isSubstring(kStr As String, f As Integer) As Integer
Dim As String fStr = Str(f)
Dim As Integer fLen = Len(fStr)
Dim As Integer result = 0
Dim As Integer fEnd = Len(kStr) - fLen + 1
For fPos As Integer = 1 To Len(kStr) - fLen + 1
If Mid(kStr, fPos, fLen) = fStr Then
result = -1
Exit For
End If
Next fPos
Return result
End Function
Dim As Integer requiredNumbers = 20
Dim As Integer kCount = 0
For k As Integer = 11 To 99999999 Step 2
If k Mod 3 <> 0 And k Mod 5 <> 0 And k Mod 7 <> 0 Then
Dim As Integer isCandidate = -1
Dim As String kStr = Str(k)
Dim As Integer v = k
Dim As Integer fCount = 0
For f As Integer = 11 To Sqr(k) + 1
If v Mod f = 0 Then
isCandidate = isSubstring(kStr, f)
If isCandidate Then
While v Mod f = 0
fCount += 1
v \= f
Wend
Else
Exit For
End If
End If
Next f
If isCandidate And (fCount > 1 Or (v <> k And v > 1)) Then
If v > 1 Then isCandidate = isSubstring(kStr, v)
If isCandidate Then
Print Using "#######,###"; k;
kCount += 1
If kCount Mod 10 = 0 Then Print
End If
End If
End If
If kCount >= requiredNumbers Then Exit For
Next k</syntaxhighlight>
{{out}}
<pre> 15,317 59,177 83,731 119,911 183,347 192,413 1,819,231 2,111,317 2,237,411 3,129,361
5,526,173 11,610,313 13,436,683 13,731,373 13,737,841 13,831,103 15,813,251 17,692,313 19,173,071 28,118,827</pre>
=={{header|Go}}==
Line 312 ⟶ 563:
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) {
List<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;
}
final 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}}==
Line 353 ⟶ 688:
We use a sieve to build a list of prime factors. This is more efficient than computing the list of prime factors on the fly.
To find the
<syntaxhighlight lang="Nim">import std/[strformat, strutils]
Line 372 ⟶ 707:
primeFactors(k).add n
const N =
var n = 11 * 11
var count = 0
Line 407 ⟶ 742:
19: 19_173_071
20: 28_118_827
</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang="PARI/GP">
/* Returns a substring of str starting at s with length n */
ssubstr(str, s = 1, n = 0) = {
my(vt = Vecsmall(str), ve, vr, vtn = #str, n1);
if (vtn == 0, return(""));
if (s < 1 || s > vtn, return(str));
n1 = vtn - s + 1; if (n == 0, n = n1); if (n > n1, n = n1);
ve = vector(n, z, z - 1 + s); vr = vecextract(vt, ve); return(Strchr(vr));
}
/* Checks if subStr is a substring of mainStr */
isSubstring(mainStr, subStr) = {
mainLen = #Vecsmall(mainStr);
subLen = #Vecsmall(subStr);
for (startPos = 1, mainLen - subLen + 1,
if (ssubstr(mainStr, startPos, subLen) == subStr,
return(1); /* True: subStr found in mainStr */
)
);
return(0); /* False: subStr not found */
}
/* Determines if a number's factors, all > 9, are substrings of its decimal representation */
contains_its_prime_factors_all_over_9(n) = {
if (n < 10 || isprime(n), return(0)); /* Skip if n < 10 or n is prime */
strn = Str(n); /* Convert n to string */
pfacs = factor(n)[, 1]; /* Get unique prime factors of n */
for (i = 1, #pfacs,
if (pfacs[i] <= 9, return(0)); /* Skip factors ≤ 9 */
if (!isSubstring(strn, Str(pfacs[i])), return(0)); /* Check if factor is a substring */
);
return(1); /* All checks passed */
}
/* Main loop to find and print numbers meeting the criteria */
{
found = 0; /* Counter for numbers found */
for (n = 0, 30 * 10^6, /* Iterate from 0 to 30 million */
if (contains_its_prime_factors_all_over_9(n),
found += 1; /* Increment counter if n meets criteria */
print1(n, " "); /* Print n followed by a space */
if (found % 10 == 0, print("")); /* Newline every 10 numbers */
if (found == 20, break); /* Stop after finding 20 numbers */
);
);
}
</syntaxhighlight>
{{out}}
<pre>
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361
5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827
</pre>
Line 1,129 ⟶ 1,513:
<pre> 15,317 59,177 83,731 119,911 183,347 192,413 1,819,231 2,111,317 2,237,411 3,129,361
5,526,173 11,610,313 13,436,683 13,731,373 13,737,841 13,831,103 15,813,251 17,692,313 19,173,071 28,118,827</pre>
=={{header|RPL}}==
{{works with|HP|49}}
≪ '''IF''' DUP ISPRIME? '''THEN''' DROP <span style="color:red">0</span> '''ELSE'''
DUP FACTORS DUP SIZE
ROT →STR → n
≪ { }
<span style="color:red">1</span> ROT '''FOR''' j
OVER j GET →STR + <span style="color:grey">@ extract prime factors and convert into strings</span>
<span style="color:red">2</span> '''STEP''' NIP
≪ n SWAP POS ≫ MAP <span style="color:red">1</span> + ΠLIST <span style="color:grey">@ + 1 to avoid arror with singletons</span>
≫
'''END'''
≫ '<span style="color:blue">MATRIOSHKA?</span>' STO
≪ 999999999 → max
≪ { }
<span style="color:red">11 </span>max '''FOR''' j
'''IF''' j <span style="color:red">105</span> GCD 1 == '''THEN''' <span style="color:grey">@ if no single digit factor</span>
'''IF''' j <span style="color:blue">MATRIOSHKA?</span> '''THEN'''
j +
'''IF''' DUP SIZE <span style="color:red">6</span> == '''THEN''' max 'j' STO '''END'''
'''END'''
'''END'''
<span style="color:red">2</span> '''STEP'''
≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: {15317 59177 83731 119911 183347 192413}
</pre>
Finding the first six numbers takes 4 minutes 20 seconds with an iOS HP-49 emulator, meaning that about two hours would be required to get ten. We're gonna need a bigger boat.
=={{header|Ruby}}==
Line 1,158 ⟶ 1,573:
3129361
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">use primes::{is_prime,factors_uniq};
/// True if non-prime n's factors, all > 9, are all substrings of its representation in base 10
fn contains_its_prime_factors_all_over_7(n: u64) -> bool {
if n < 10 || is_prime(n) {
return false;
}
let strn = &n.to_string();
let pfacs = factors_uniq(n);
return pfacs.iter().all(|f| f > &9 && strn.contains(&f.to_string()));
}
fn main() {
let mut found = 0;
// 20 of these < 30 million
for n in 0..30_000_000 {
if contains_its_prime_factors_all_over_7(n) {
found += 1;
print!("{:12}{}", n, {if found % 10 == 0 {"\n"} else {""}});
if found == 20 {
break;
}
}
}
}
</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|Scala}}==
for Scala3
<syntaxhighlight lang="scala">
def isComposite(num: Int): Boolean = {
val numStr = num.toString
def iter(n: Int, start: Int): Boolean = {
val limit = math.sqrt(n).floor.toInt
(start to limit by 2).dropWhile(n % _ > 0).headOption match {
case Some(v) if v < 10 => false
case Some(v) =>
if (v == start || numStr.contains(v.toString)) iter(n / v, v)
else false
case None => n < num && numStr.contains(n.toString)
}
}
iter(num, 3)
}
def composites = Iterator.from(121, 2).filter(isComposite(_))
@main def main = {
val start = System.currentTimeMillis
composites.take(20)
.grouped(10)
.foreach(grp => println(grp.map("%8d".format(_)).mkString(" ")))
val time = System.currentTimeMillis - start
println(s"time elapsed: $time ms")
}
</syntaxhighlight>
{{out}}
<pre>
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361
5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827
time elapsed: 59821 ms
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var e = Enumerator({|f|
Line 1,198 ⟶ 1,681:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./seq" for Lst
import "./fmt" for Fmt
var count = 0
| |||