Rosetta Code

Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions

Page Discussion

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

17,586 bytes added ,  2 months ago
Added FreeBASIC
m (syntax highlighting fixup automation)
(Added FreeBASIC)
 
(24 intermediate revisions by 12 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}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Brute force method with a few obvious optimizations. Could be speeded up a lot, with some work.
 
<syntaxhighlight lang="Delphi">
 
 
 
procedure MultidigitComposites(Memo: TMemo);
var I,Cnt: integer;
var IA: TIntegerDynArray;
var Sieve: TPrimeSieve;
 
 
function MatchCriteria(N: integer): boolean;
{Test N against Criteria}
var I,L: integer;
var SN,ST: string;
begin
Result:=False;
{No even numbers}
if (N and 1)=0 then exit;
{N can't be prime}
if Sieve[N] then exit;
I:=3;
SN:=IntToStr(N);
repeat
begin
{Is it a factor }
if (N mod I) = 0 then
begin
{No one-digit numbers}
if I<10 then exit;
{Factor string must be found in N's string}
ST:=IntToStr(I);
if Pos(ST,SN)<1 then exit;
N:=N div I;
end
else I:=I+2;
end
until N<=1;
Result:=True;
end;
 
 
begin
Sieve:=TPrimeSieve.Create;
try
{Create 30 million primes}
Sieve.Intialize(30000000);
Cnt:=0;
{Smallest prime factor}
I:=11*11;
while I<High(integer) do
begin
{Test if I matches criteria}
if MatchCriteria(I) then
begin
Inc(Cnt);
Memo.Lines.Add(IntToStr(Cnt)+' - '+FloatToStrF(I,ffNumber,18,0));
if Cnt>=20 then break;
end;
Inc(I,2);
end;
finally Sieve.Free; end;
end;
 
</syntaxhighlight>
{{out}}
<pre>
1 - 15,317
2 - 59,177
3 - 83,731
4 - 119,911
5 - 183,347
6 - 192,413
7 - 1,819,231
8 - 2,111,317
9 - 2,237,411
10 - 3,129,361
11 - 5,526,173
12 - 11,610,313
13 - 13,436,683
14 - 13,731,373
15 - 13,737,841
16 - 13,831,103
17 - 15,813,251
18 - 17,692,313
19 - 19,173,071
20 - 28,118,827
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 143 ⟶ 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 218 ⟶ 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 255 ⟶ 684:
{{out}}
<pre>{15317, 59177, 83731, 119911, 183347, 192413, 1819231, 2111317, 2237411, 3129361, 5526173, 11610313, 13436683, 13731373, 13737841, 13831103, 15813251, 17692313, 19173071, 28118827}</pre>
 
=={{header|Nim}}==
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 20 first elements of the sequence, the program takes less than 10 seconds on an Intel Core I5-8250U 4×1.6GHz.
<syntaxhighlight lang="Nim">import std/[strformat, strutils]
 
const Max = 80_000_000 # Maximal value for composite number.
 
# Prime factors of odd numbers.
# If a number is prime, its factor list is empty.
var factors: array[0..(Max - 3) div 2, seq[uint32]]
 
template primeFactors(n: Natural): seq[uint32] =
factors[(n - 3) shr 1]
 
# Build the list of factors.
for n in countup(3u32, Max div 11, 2):
if primeFactors(n).len == 0:
# "n" is prime.
for k in countup(n + n + n, Max, 2 * n):
primeFactors(k).add n
 
const N = 20 # Number of results.
var n = 11 * 11
var count = 0
while count < N:
if primeFactors(n).len > 0:
let nStr = $n
block Check:
for f in primeFactors(n):
if f < 11 or $f notin nStr: break Check
inc count
echo &"{count:2}: {insertSep($n)}"
inc n, 2
</syntaxhighlight>
 
{{out}}
<pre> 1: 15_317
2: 59_177
3: 83_731
4: 119_911
5: 183_347
6: 192_413
7: 1_819_231
8: 2_111_317
9: 2_237_411
10: 3_129_361
11: 5_526_173
12: 11_610_313
13: 13_436_683
14: 13_731_373
15: 13_737_841
16: 13_831_103
17: 15_813_251
18: 17_692_313
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>
 
=={{header|Pascal}}==
Line 971 ⟶ 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}}==
<syntaxhighlight lang="ruby">require 'prime'
 
generator2357 = Enumerator.new do |y|
gen23 = Prime::Generator23.new
gen23.each {|n| y << n unless (n%5 == 0 || n%7 == 0) }
end
 
res = generator2357.lazy.select do |n|
primes, exp = n.prime_division.transpose
next if exp.sum < 2 #exclude primes
s = n.to_s
primes.all?{|pr| s.match?(-pr.to_s) }
end
 
res.take(10).each{|n| puts n}</syntaxhighlight>
{{out}}
<pre>15317
59177
83731
119911
183347
192413
1819231
2111317
2237411
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}}==
Line 1,012 ⟶ 1,681:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
 
var count = 0
Jjuanhdez
2,122

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327265...355355"