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
(Added FreeBASIC) |
|||
| (13 intermediate revisions by 7 users not shown) | |||
Line 166:
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 260 ⟶ 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 294 ⟶ 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 405 ⟶ 599:
private static List<Integer> primeFactors(int aK) {
if ( aK <= 1 ) {
return result;
Line 416 ⟶ 610:
}
final int divisor = pollardsRho(bigK).intValueExact();
result.addAll(primeFactors(divisor));
result.addAll(primeFactors(aK / divisor));
Line 548 ⟶ 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,265 ⟶ 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,333 ⟶ 1,612:
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) =>
Line 1,341 ⟶ 1,620:
}
}
iter(num,
}
def
@main def main = {
Line 1,359 ⟶ 1,638:
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361
5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827
time elapsed:
</pre>
Line 1,402 ⟶ 1,681:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./seq" for Lst
import "./fmt" for Fmt
var count = 0
| |||