Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
Content added Content deleted
(→{{header|Perl}}: prepend pascal version reused http://rosettacode.org/wiki/Factors_of_an_integer#using_Prime_decomposition) |
m (→{{header|Free Pascal}}: tested til 1E10) |
||
Line 195: | Line 195: | ||
chk,p,i: NativeInt; |
chk,p,i: NativeInt; |
||
Begin |
Begin |
||
str(n,s); |
str(n:12,s); |
||
result := s+': '; |
result := s+': '; |
||
with pd^ do |
with pd^ do |
||
Line 409: | Line 409: | ||
T0:Int64; |
T0:Int64; |
||
n,i : NativeUInt; |
n,i,cnt : NativeUInt; |
||
checked : boolean; |
checked : boolean; |
||
Begin |
Begin |
||
Line 415: | Line 415: | ||
T0 := GetTickCount64; |
T0 := GetTickCount64; |
||
cnt := 0; |
|||
n := 0; |
n := 0; |
||
Init_Sieve( |
Init_Sieve(n); |
||
repeat |
repeat |
||
pPrimeDecomp:= GetNextPrimeDecomp; |
pPrimeDecomp:= GetNextPrimeDecomp; |
||
Line 422: | Line 423: | ||
begin |
begin |
||
//composite with smallest factor 11 |
//composite with smallest factor 11 |
||
if (pfDivCnt> |
if (pfDivCnt>=4) AND (pfpotPrimIdx[0]>3) then |
||
begin |
begin |
||
str(n,s); |
str(n,s); |
||
Line 434: | Line 435: | ||
if checked then |
if checked then |
||
begin |
begin |
||
//writeln(cnt:4,OutPots(pPrimeDecomp,n)); |
|||
if pfRemain >1 then |
if pfRemain >1 then |
||
begin |
begin |
||
Line 440: | Line 442: | ||
end; |
end; |
||
if checked then |
if checked then |
||
begin |
|||
inc(cnt); |
|||
writeln(cnt:4,OutPots(pPrimeDecomp,n)); |
|||
end; |
|||
end; |
end; |
||
end; |
end; |
||
end; |
end; |
||
inc(n); |
inc(n); |
||
until n > 28118827;//1000*1000*1000+1;// |
until n > 28118827;//10*1000*1000*1000+1;// |
||
T0 := GetTickCount64-T0; |
T0 := GetTickCount64-T0; |
||
writeln('runtime ',T0/1000:0:3,' s'); |
writeln('runtime ',T0/1000:0:3,' s'); |
||
Line 451: | Line 456: | ||
</lang> |
</lang> |
||
{{out|@TIO.RUN}} |
{{out|@TIO.RUN}} |
||
<pre style="height:480px"> |
|||
<pre> |
|||
Real time: 2.166 s CPU share: 99.20 %//500*1000*1000 Real time: 38.895 s CPU share: 99.28 % |
Real time: 2.166 s CPU share: 99.20 %//500*1000*1000 Real time: 38.895 s CPU share: 99.28 % |
||
1 15317: 17^2*53 |
|||
2 59177: 17*59^2 |
|||
3 83731: 31*37*73 |
|||
4 119911: 11^2*991 |
|||
5 183347: 47^2*83 |
|||
6 192413: 13*19^2*41 |
|||
7 1819231: 19*23^2*181 |
|||
8 2111317: 13^3*31^2 |
|||
1819231 : 12 : 19*23^2*181 |
|||
9 2237411: 11^3*41^2 |
|||
10 3129361: 29^2*61^2 |
|||
11 5526173: 17*61*73^2 |
|||
12 11610313: 11^4*13*61 |
|||
13 13436683: 13^2*43^3 |
|||
11610313 : 20 : 11^4*13*61 |
|||
14 13731373: 73*137*1373 |
|||
13436683 : 12 : 13^2*43^3 |
|||
15 13737841: 13^5*37 |
|||
13731373 : 8 : 73*137*1373 |
|||
16 13831103: 11*13*311^2 |
|||
13737841 : 12 : 13^5*37 |
|||
17 15813251: 251^3 |
|||
13831103 : 12 : 11*13*311^2 |
|||
18 17692313: 23*769231 |
|||
15813251 : 4 : 251^3 |
|||
19 19173071: 19^2*173*307 |
|||
17692313 : 4 : 23*769231 |
|||
20 28118827: 11^2*281*827 |
|||
28118827 : 12 : 11^2*281*827 |
|||
runtime 2.011 s |
runtime 2.011 s |
||
..@home limit 1E9 53^2*89xprime appears often |
|||
//@home til 1E10 .. 188 9898707359: 59^2*89^2*359 |
|||
21 31373137: 73*137*3137 |
|||
889253557 889253557 : 12 : 53^2*89*3557 |
|||
22 47458321: 83^4 |
|||
889753559 889753559 : 12 : 53^2*89*3559 |
|||
23 55251877: 251^2*877 |
|||
24 62499251: 251*499^2 |
|||
892961737 892961737 : 24 : 17^2*37^3*61 |
|||
25 79710361: 103*797*971 |
|||
895253581 895253581 : 12 : 53^2*89*3581 |
|||
26 81227897: 89*97^3 |
|||
27 97337269: 37^2*97*733 |
|||
28 103192211: 19^2*31*9221 |
|||
29 107132311: 11^2*13^4*31 |
|||
30 119503483: 11*19*83^3 |
|||
runtime 45.922 s |
|||
31 119759299: 11*19*29*19759 |
|||
32 124251499: 499^3 |
|||
33 131079601: 107^4 |
|||
34 142153597: 59^2*97*421 |
|||
35 147008443: 43^5 |
|||
36 171197531: 17^2*31*97*197 |
|||
37 179717969: 71*79*179^2 |
|||
38 183171409: 71*1409*1831 |
|||
39 215797193: 19*1579*7193 |
|||
40 241153517: 11*17*241*5351 |
|||
41 248791373: 73*373*9137 |
|||
42 261113281: 11^2*13^2*113^2 |
|||
43 272433191: 19*331*43319 |
|||
44 277337147: 71*73^2*733 |
|||
45 291579719: 19*1579*9719 |
|||
46 312239471: 31^3*47*223 |
|||
47 344972429: 29*3449^2 |
|||
48 364181311: 13^4*41*311 |
|||
49 381317911: 13^6*79 |
|||
50 385494799: 47^4*79 |
|||
51 392616923: 23^5*61 |
|||
52 399311341: 11*13^4*31*41 |
|||
53 410963311: 11^2*31*331^2 |
|||
54 413363353: 13^4*41*353 |
|||
55 423564751: 751^3 |
|||
56 471751831: 31*47^2*83^2 |
|||
57 492913739: 73*739*9137 |
|||
58 501225163: 163*251*12251 |
|||
59 591331169: 11*13^2*31^2*331 |
|||
60 592878929: 29^2*89^3 |
|||
61 594391193: 11*19^2*43*59^2 |
|||
62 647959343: 47^3*79^2 |
|||
63 717528911: 11^2*17^4*71 |
|||
64 723104383: 23^2*43*83*383 |
|||
65 772253089: 53^2*89*3089 |
|||
66 799216219: 79^3*1621 |
|||
67 847253389: 53^2*89*3389 |
|||
68 889253557: 53^2*89*3557 |
|||
69 889753559: 53^2*89*3559 |
|||
70 892753571: 53^2*89*3571 |
|||
71 892961737: 17^2*37^3*61 |
|||
72 895253581: 53^2*89*3581 |
|||
73 895753583: 53^2*89*3583 |
|||
74 898253593: 53^2*89*3593 |
|||
75 972253889: 53^2*89*3889 |
|||
76 997253989: 53^2*89*3989 |
|||
77 1005371999: 53^2*71^3 |
|||
78 1011819919: 11*101*919*991 |
|||
79 1019457337: 37^2*73*101^2 |
|||
80 1029761609: 29^2*761*1609 |
|||
81 1031176157: 11^2*17*31*103*157 |
|||
82 1109183317: 11*31^2*317*331 |
|||
83 1119587711: 11^2*19^4*71 |
|||
84 1137041971: 13^4*41*971 |
|||
85 1158169331: 11*31^2*331^2 |
|||
86 1161675547: 47^3*67*167 |
|||
87 1189683737: 11^5*83*89 |
|||
88 1190911909: 11*9091*11909 |
|||
89 1193961571: 11^3*571*1571 |
|||
90 1274418211: 11*41^5 |
|||
91 1311979279: 13^2*19*131*3119 |
|||
92 1316779217: 13^2*17*677^2 |
|||
93 1334717327: 47*73^4 |
|||
94 1356431947: 13*43^2*56431 |
|||
95 1363214333: 13^3*433*1433 |
|||
96 1371981127: 11^2*19*37*127^2 |
|||
97 1379703847: 47^3*97*137 |
|||
98 1382331137: 11*31*37*331^2 |
|||
99 1389214193: 41*193*419^2 |
|||
100 1497392977: 97*3929^2 |
|||
101 1502797333: 733^2*2797 |
|||
102 1583717977: 17^2*71*79*977 |
|||
103 1593519731: 59*5197^2 |
|||
104 1713767399: 17^6*71 |
|||
105 1729719587: 17*19^2*29*9719 |
|||
106 1733793487: 79^2*379*733 |
|||
107 1761789373: 17^2*37^2*61*73 |
|||
108 1871688013: 13^5*71^2 |
|||
109 1907307719: 71^3*73^2 |
|||
110 1948441249: 1249^3 |
|||
111 1963137527: 13*31^3*37*137 |
|||
112 1969555417: 17*41^5 |
|||
113 1982119441: 211^4 |
|||
114 1997841197: 11*97^3*199 |
|||
115 2043853681: 53^2*853^2 |
|||
116 2070507919: 19^2*79^2*919 |
|||
117 2073071593: 73^5 |
|||
118 2278326179: 17*83*617*2617 |
|||
119 2297126743: 29^3*97*971 |
|||
120 2301131209: 13^4*23*31*113 |
|||
121 2323519823: 19^2*23^5 |
|||
122 2371392959: 13^2*29*59^2*139 |
|||
123 2647985311: 31*47*53^2*647 |
|||
124 2667165611: 11^5*16561 |
|||
125 2722413361: 241*3361^2 |
|||
126 2736047519: 19^2*47^3*73 |
|||
127 2881415311: 31^3*311^2 |
|||
128 2911317539: 13^2*31*317*1753 |
|||
129 2924190611: 19^3*29*61*241 |
|||
130 3015962419: 41*419^3 |
|||
131 3112317013: 13^2*23^2*31*1123 |
|||
132 3131733761: 13^2*17^2*37*1733 |
|||
133 3150989441: 41*509*150989 |
|||
134 3151811881: 31^2*1811^2 |
|||
135 3423536177: 17*23^2*617^2 |
|||
136 3461792569: 17^2*3461^2 |
|||
137 3559281161: 281*3559^2 |
|||
138 3730774997: 499*997*7499 |
|||
139 3795321361: 13*37*53^4 |
|||
140 3877179289: 71^2*877^2 |
|||
141 4070131949: 13^2*19*31^2*1319 |
|||
142 4134555661: 41^2*61^2*661 |
|||
143 4143189277: 31*41^2*43^3 |
|||
144 4162322419: 19^5*41^2 |
|||
145 4311603593: 11*43^2*59*3593 |
|||
146 4339091119: 11*4339*90911 |
|||
147 4340365711: 11^3*571*5711 |
|||
148 4375770311: 11^4*31^2*311 |
|||
149 4427192717: 17*19*71^2*2719 |
|||
150 4530018503: 503*3001^2 |
|||
151 4541687137: 13*37*41^3*137 |
|||
152 4541938631: 41*419^2*631 |
|||
153 4590757613: 13*613*757*761 |
|||
154 4750104241: 41^6 |
|||
155 4796438239: 23^3*479*823 |
|||
156 4985739599: 59*8573*9857 |
|||
157 5036760823: 23^3*503*823 |
|||
158 5094014879: 79*401^3 |
|||
159 5107117543: 11^4*17^3*71 |
|||
160 5137905383: 13^2*53^2*79*137 |
|||
161 5181876331: 31^5*181 |
|||
162 5276191811: 11^5*181^2 |
|||
163 5319967909: 19*53^2*99679 |
|||
164 5411964371: 11*41^2*541^2 |
|||
165 5445241447: 41^5*47 |
|||
166 5892813173: 13^3*17^2*9281 |
|||
167 6021989371: 19^3*937^2 |
|||
168 6122529619: 19*29^2*619^2 |
|||
169 6138239333: 23^3*613*823 |
|||
170 6230438329: 23*29^4*383 |
|||
171 6612362989: 23^4*23629 |
|||
172 6645125311: 11^8*31 |
|||
173 7155432157: 43^2*157^3 |
|||
174 7232294717: 17*29^2*47^2*229 |
|||
175 7293289141: 29*41^4*89 |
|||
176 7491092411: 11*41^4*241 |
|||
177 8144543377: 433*4337^2 |
|||
178 8194561699: 19*4561*94561 |
|||
179 8336743231: 23^4*31^3 |
|||
180 8413553317: 13*17*53^2*13553 |
|||
181 8435454179: 17*43^3*79^2 |
|||
182 8966127229: 29^2*127^2*661 |
|||
183 9091190911: 11*9091*90911 |
|||
184 9373076171: 37^2*937*7307 |
|||
185 9418073141: 31*41^2*180731 |
|||
186 9419992843: 19^4*41^2*43 |
|||
187 9523894717: 17^3*23*89*947 |
|||
188 9898707359: 59^2*89^2*359 |
|||
runtime 539.800 s |
|||
</pre> |
</pre> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |