Odd squarefree semiprimes: Difference between revisions
(Added Easylang) |
|||
(24 intermediate revisions by 13 users not shown) | |||
Line 4: | Line 4: | ||
;Task: |
;Task: |
||
Odd numbers of the form p*q where p and q are distinct primes, where '''p*q < 1000''' |
Odd numbers of the form p*q where p and q are distinct primes, where '''p*q < 1000''' |
||
;See also |
|||
:* [[oeis:A046388|OEIS:A046388]] |
|||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="11l">F odd_square_free_semiprime(=n) |
|||
I n % 2 == 0 |
|||
R 0B |
|||
V count = 0 |
|||
V i = 3 |
|||
L i * i <= n |
|||
L n % i == 0 |
|||
I ++count > 1 |
|||
R 0B |
|||
n I/= i |
|||
i += 2 |
|||
R count == 1 |
|||
print(‘Odd square-free semiprimes < 1000:’) |
|||
V count = 0 |
|||
L(i) (1.<1000).step(2) |
|||
I odd_square_free_semiprime(i) |
|||
print(‘#4’.format(i), end' ‘’) |
|||
I ++count % 20 == 0 |
|||
print() |
|||
print("\nCount: "count)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Odd square-free semiprimes < 1000: |
|||
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
|||
129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 |
|||
221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 |
|||
327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 |
|||
437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 |
|||
533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 |
|||
635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 |
|||
731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 |
|||
817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 |
|||
933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
|||
Count: 194 |
|||
</pre> |
|||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
{{libheader|Action! Tool Kit}} |
{{libheader|Action! Tool Kit}} |
||
{{libheader|Action! Sieve of Eratosthenes}} |
{{libheader|Action! Sieve of Eratosthenes}} |
||
< |
<syntaxhighlight lang="action!">INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit |
||
INCLUDE "H6:SIEVE.ACT" |
INCLUDE "H6:SIEVE.ACT" |
||
Line 41: | Line 87: | ||
OD |
OD |
||
PrintF("%E%EThere are %I odd numbers",count) |
PrintF("%E%EThere are %I odd numbers",count) |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Odd_squarefree_semiprimes.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Odd_squarefree_semiprimes.png Screenshot from Atari 8-bit computer] |
||
Line 57: | Line 103: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find some odd square free semi-primes # |
||
# numbers of the form p*q where p =/= q and p, q are prime # |
# numbers of the form p*q where p =/= q and p, q are prime # |
||
# reurns a list of primes up to n # |
# reurns a list of primes up to n # |
||
Line 97: | Line 143: | ||
FI |
FI |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 114: | Line 160: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">primes: select 0..1000 => prime? |
||
lst: sort unique flatten map primes 'p [ |
lst: sort unique flatten map primes 'p [ |
||
map select primes 'q -> all? @[odd? p*q p<>q 1000>p*q]=>[p*&] |
map select primes 'q -> all? @[odd? p*q p<>q 1000>p*q]=>[p*&] |
||
] |
] |
||
loop split.every:10 lst 'a -> |
loop split.every:10 lst 'a -> |
||
print map a => [pad to :string & 4]</ |
print map a => [pad to :string & 4]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 145: | Line 191: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f ODD_SQUAREFREE_SEMIPRIMES.AWK |
# syntax: GAWK -f ODD_SQUAREFREE_SEMIPRIMES.AWK |
||
# converted from C++ |
# converted from C++ |
||
Line 172: | Line 218: | ||
return(count==1) |
return(count==1) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 203: | Line 249: | ||
Use the function from [[Primality by trial division#FreeBASIC]] as an include. This code generates the odd squarefree semiprimes in ascending order of their first factor, then their second. |
Use the function from [[Primality by trial division#FreeBASIC]] as an include. This code generates the odd squarefree semiprimes in ascending order of their first factor, then their second. |
||
< |
<syntaxhighlight lang="freebasic">#include "isprime.bas" |
||
dim as integer p, q |
dim as integer p, q |
||
for p = 3 to 999 |
for p = 3 to 999 |
||
Line 211: | Line 257: | ||
print p*q;" "; |
print p*q;" "; |
||
next q |
next q |
||
next p</ |
next p</syntaxhighlight> |
||
{{out}}<pre> 15 21 33 39 51 57 69 87 93 111 123 129 141 159 177 183 201 213 219 237 249 267 291 303 309 321 327 339 381 393 411 417 447 453 471 489 501 519 537 543 573 579 591 597 633 669 681 687 699 717 723 753 771 789 807 813 831 843 849 879 921 933 939 951 993 35 55 65 85 95 115 145 155 185 205 215 235 265 295 305 335 355 365 395 415 445 485 505 515 535 545 565 635 655 685 695 745 755 785 815 835 865 895 905 955 965 985 995 77 91 119 133 161 203 217 259 287 301 329 371 413 427 469 497 511 553 581 623 679 707 721 749 763 791 889 917 959 973 143 187 209 253 319 341 407 451 473 517 583 649 671 737 781 803 869 913 979 221 247 299 377 403 481 533 559 611 689 767 793 871 923 949 323 391 493 527 629 697 731 799 901 437 551 589 703 779 817 893 667 713 851 943 989 899</pre> |
{{out}}<pre> 15 21 33 39 51 57 69 87 93 111 123 129 141 159 177 183 201 213 219 237 249 267 291 303 309 321 327 339 381 393 411 417 447 453 471 489 501 519 537 543 573 579 591 597 633 669 681 687 699 717 723 753 771 789 807 813 831 843 849 879 921 933 939 951 993 35 55 65 85 95 115 145 155 185 205 215 235 265 295 305 335 355 365 395 415 445 485 505 515 535 545 565 635 655 685 695 745 755 785 815 835 865 895 905 955 965 985 995 77 91 119 133 161 203 217 259 287 301 329 371 413 427 469 497 511 553 581 623 679 707 721 749 763 791 889 917 959 973 143 187 209 253 319 341 407 451 473 517 583 649 671 737 781 803 869 913 979 221 247 299 377 403 481 533 559 611 689 767 793 871 923 949 323 391 493 527 629 697 731 799 901 437 551 589 703 779 817 893 667 713 851 943 989 899</pre> |
||
==={{header|Tiny BASIC}}=== |
==={{header|Tiny BASIC}}=== |
||
< |
<syntaxhighlight lang="tinybasic"> LET P = 1 |
||
10 LET P = P + 2 |
10 LET P = P + 2 |
||
LET Q = P |
LET Q = P |
||
Line 236: | Line 282: | ||
LET I = I + 1 |
LET I = I + 1 |
||
IF I*I <= A THEN GOTO 110 |
IF I*I <= A THEN GOTO 110 |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
=={{header|C#|CSharp}}== |
=={{header|C#|CSharp}}== |
||
This reveals a set of semi-prime numbers (with exactly two factors for each '''<big>''n''</big>'''), where '''<big>''1 < p < q < n''</big>'''. It is square-free, since '''<big>''p < q''</big>'''. |
This reveals a set of semi-prime numbers (with exactly two factors for each '''<big>''n''</big>'''), where '''<big>''1 < p < q < n''</big>'''. It is square-free, since '''<big>''p < q''</big>'''. |
||
< |
<syntaxhighlight lang="csharp">using System; using static System.Console; using System.Collections; |
||
using System.Linq; using System.Collections.Generic; |
using System.Linq; using System.Collections.Generic; |
||
Line 256: | Line 302: | ||
if (!flags[j]) { yield return j; |
if (!flags[j]) { yield return j; |
||
for (int k = sq, i = j << 1; k <= lim; k += i) flags[k] = true; } |
for (int k = sq, i = j << 1; k <= lim; k += i) flags[k] = true; } |
||
for (; j <= lim; j += 2) if (!flags[j]) yield return j; } }</ |
for (; j <= lim; j += 2) if (!flags[j]) yield return j; } }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
<pre> 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
||
Line 272: | Line 318: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <iomanip> |
||
#include <iostream> |
#include <iostream> |
||
Line 302: | Line 348: | ||
std::cout << "\nCount: " << count << '\n'; |
std::cout << "\nCount: " << count << '\n'; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 318: | Line 364: | ||
933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
||
Count: 194 |
Count: 194 |
||
</pre> |
|||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
function IsPrime(N: int64): boolean; |
|||
{Fast, optimised prime test} |
|||
var I,Stop: int64; |
|||
begin |
|||
if (N = 2) or (N=3) then Result:=true |
|||
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false |
|||
else |
|||
begin |
|||
I:=5; |
|||
Stop:=Trunc(sqrt(N+0.0)); |
|||
Result:=False; |
|||
while I<=Stop do |
|||
begin |
|||
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit; |
|||
Inc(I,6); |
|||
end; |
|||
Result:=True; |
|||
end; |
|||
end; |
|||
function CustomSort (Item1, Item2: Pointer): Integer; |
|||
begin |
|||
Result:=integer(Item1)-integer(Item2); |
|||
end; |
|||
procedure OddSquareFreeSemiprimes(Memo: TMemo); |
|||
var P,Q,I: integer; |
|||
const Limit = 1000; |
|||
var LS: TList; |
|||
var S: string; |
|||
begin |
|||
LS:=TList.Create; |
|||
try |
|||
P:=1; |
|||
{Test all relevant combinations of P and Q} |
|||
for P:=1 to Limit div 5 do |
|||
begin |
|||
if ((P and 1)=0) or (not IsPrime(P)) then continue; |
|||
for Q:=P+2 to Limit div P do |
|||
begin |
|||
if ((Q and 1)=0) or (not IsPrime(Q)) then continue; |
|||
{Put in list} |
|||
LS.Add(Pointer(P*Q)) |
|||
end; |
|||
end; |
|||
{List is not in order, so sort it} |
|||
LS.Sort(CustomSort); |
|||
S:=''; |
|||
for I:=0 to LS.Count-1 do |
|||
begin |
|||
S:=S+Format('%8D',[Integer(LS[I])]); |
|||
If (I mod 5)=4 then S:=S+CRLF; |
|||
end; |
|||
Memo.Lines.Add(S); |
|||
Memo.Lines.Add('Count='+IntToStr(LS.Count)); |
|||
finally LS.Free; end; |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
15 21 33 35 39 |
|||
51 55 57 65 69 |
|||
77 85 87 91 93 |
|||
95 111 115 119 123 |
|||
129 133 141 143 145 |
|||
155 159 161 177 183 |
|||
185 187 201 203 205 |
|||
209 213 215 217 219 |
|||
221 235 237 247 249 |
|||
253 259 265 267 287 |
|||
291 295 299 301 303 |
|||
305 309 319 321 323 |
|||
327 329 335 339 341 |
|||
355 365 371 377 381 |
|||
391 393 395 403 407 |
|||
411 413 415 417 427 |
|||
437 445 447 451 453 |
|||
469 471 473 481 485 |
|||
489 493 497 501 505 |
|||
511 515 517 519 527 |
|||
533 535 537 543 545 |
|||
551 553 559 565 573 |
|||
579 581 583 589 591 |
|||
597 611 623 629 633 |
|||
635 649 655 667 669 |
|||
671 679 681 685 687 |
|||
689 695 697 699 703 |
|||
707 713 717 721 723 |
|||
731 737 745 749 753 |
|||
755 763 767 771 779 |
|||
781 785 789 791 793 |
|||
799 803 807 813 815 |
|||
817 831 835 843 849 |
|||
851 865 869 871 879 |
|||
889 893 895 899 901 |
|||
905 913 917 921 923 |
|||
933 939 943 949 951 |
|||
955 959 965 973 979 |
|||
985 989 993 995 |
|||
Count=194 |
|||
Elapsed Time: 9.048 ms. |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
func oddsemi n . |
|||
i = 3 |
|||
while i <= sqrt n |
|||
while n mod i = 0 |
|||
count += 1 |
|||
if count > 1 |
|||
return 0 |
|||
. |
|||
n = n div i |
|||
. |
|||
i += 2 |
|||
. |
|||
return if count = 1 |
|||
. |
|||
for i = 1 step 2 to 999 |
|||
if oddsemi i = 1 |
|||
write i & " " |
|||
. |
|||
. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
|||
<syntaxhighlight lang="fsharp"> |
|||
// Odd squarefree semiprimes. Nigel Galloway: January 4th., 2023 |
|||
let n=primes32()|>Seq.skip 1|>Seq.takeWhile((>)333)|>List.ofSeq |
|||
List.allPairs n n|>Seq.filter(fun(n,g)->n<g)|>Seq.map(fun(n,g)->n*g)|>Seq.filter((>)1000)|>Seq.iter(printf "%d "); printfn "" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
15 21 33 39 51 57 69 87 93 111 123 129 141 159 177 183 201 213 219 237 249 267 291 303 309 321 327 339 381 393 411 417 447 453 471 489 501 519 537 543 573 579 591 597 633 669 681 687 699 717 723 753 771 789 807 813 831 843 849 879 921 933 939 951 993 35 55 65 85 95 115 145 155 185 205 215 235 265 295 305 335 355 365 395 415 445 485 505 515 535 545 565 635 655 685 695 745 755 785 815 835 865 895 905 955 965 985 995 77 91 119 133 161 203 217 259 287 301 329 371 413 427 469 497 511 553 581 623 679 707 721 749 763 791 889 917 959 973 143 187 209 253 319 341 407 451 473 517 583 649 671 737 781 803 869 913 979 221 247 299 377 403 481 533 559 611 689 767 793 871 923 949 323 391 493 527 629 697 731 799 901 437 551 589 703 779 817 893 667 713 851 943 989 899 |
|||
</pre> |
</pre> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2021-02-05}} |
{{works with|Factor|0.99 2021-02-05}} |
||
< |
<syntaxhighlight lang="factor">USING: combinators.short-circuit formatting grouping io kernel |
||
math.primes.factors math.ranges prettyprint sequences sets ; |
math.primes.factors math.ranges prettyprint sequences sets ; |
||
Line 333: | Line 535: | ||
999 odd-sfs-upto dup length |
999 odd-sfs-upto dup length |
||
"Found %d odd square-free semiprimes < 1000:\n" printf |
"Found %d odd square-free semiprimes < 1000:\n" printf |
||
20 group [ [ "%4d" printf ] each nl ] each nl</ |
20 group [ [ "%4d" printf ] each nl ] each nl</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 351: | Line 553: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{works with|Gforth}} |
{{works with|Gforth}} |
||
< |
<syntaxhighlight lang="forth">: odd-square-free-semi-prime? { n -- ? } |
||
n 1 and 0= if false exit then |
n 1 and 0= if false exit then |
||
0 { count } |
0 { count } |
||
Line 385: | Line 587: | ||
1000 special_odd_numbers |
1000 special_odd_numbers |
||
bye</ |
bye</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 406: | Line 608: | ||
{{trans|Wren}} |
{{trans|Wren}} |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 435: | Line 637: | ||
} |
} |
||
fmt.Printf("\n\n%d such numbers found.\n", len(oss)) |
fmt.Printf("\n\n%d such numbers found.\n", len(oss)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 463: | Line 665: | ||
194 such numbers found. |
194 such numbers found. |
||
</pre> |
</pre> |
||
=={{header|J}}== |
|||
<syntaxhighlight lang=J> require'stats' |
|||
(#~ 1000>])*/"1 p:1+2 comb p:inv 1000%3 |
|||
15 21 33 39 51 57 69 87 93 111 123 129 141 159 177 183 201 213 219 237 249 267 291 303 309 321 327 339 381 393 411 417 447 453 471 489 501 519 537 543 573 579 591 597 633 669 681 687 699 717 723 753 771 789 807 813 831 843 849 879 921 933 939 951 993 35 55 65 85 95 115 145 155 185 205 215 235 265 295 305 335 355 365 395 415 445 485 505 515 535 545 565 635 655 685 695 745 755 785 815 835 865 895 905 955 965 985 995 77 91 119 133 161 203 217 259 287 301 329 371 413 427 469 497 511 553 581 623 679 707 721 749 763 791 889 917 959 973 143 187 209 253 319 341 407 451 473 517 583 649 671 737 781 803 869 913 979 221 247 299 377 403 481 533 559 611 689 767 793 871 923 949 323 391 493 527 629 697 731 799 901 437 551 589 703 779 817 893 667 713 851 943 989 899</syntaxhighlight> |
|||
Note that these values are sorted in order of their smallest prime factor followed by the larger prime factor. In other words, since 899 is 29*31, and there's 8 odd primes smaller than 29, there are (conceptually speaking) 9 ascending subsequences of semiprimes here. |
|||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 470: | Line 680: | ||
See e.g. [[Erd%C5%91s-primes#jq]] for a suitable definition of `is_prime`. |
See e.g. [[Erd%C5%91s-primes#jq]] for a suitable definition of `is_prime`. |
||
< |
<syntaxhighlight lang="jq"># Output: a stream of proper square-free odd prime factors of . |
||
def proper_odd_squarefree_prime_factors: |
def proper_odd_squarefree_prime_factors: |
||
range(3; 1 + sqrt|floor) as $i |
range(3; 1 + sqrt|floor) as $i |
||
Line 492: | Line 702: | ||
| select(is_odd_squarefree_semiprime)] |
| select(is_odd_squarefree_semiprime)] |
||
| nwise(10) |
| nwise(10) |
||
| map(lpad(3)) | join(" ")</ |
| map(lpad(3)) | join(" ")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
As for [[#Arturo|Arturo]], [[#Wren|Wren]], et al. |
As for [[#Arturo|Arturo]], [[#Wren|Wren]], et al. |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
twoprimeproduct(n) = (a = factor(n).pe; length(a) == 2 && all(p -> p[2] == 1, a)) |
twoprimeproduct(n) = (a = factor(n).pe; length(a) == 2 && all(p -> p[2] == 1, a)) |
||
Line 504: | Line 714: | ||
foreach(p -> print(rpad(p[2], 4), p[1] % 20 == 0 ? "\n" : ""), enumerate(special1k)) |
foreach(p -> print(rpad(p[2], 4), p[1] % 20 == 0 ? "\n" : ""), enumerate(special1k)) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
||
Line 516: | Line 726: | ||
817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 |
817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 |
||
933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
||
</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<lang Mathematica>n = 1000; primes = Most@NestWhileList[NextPrime, 3, # < n/3 &]; |
|||
reduceList[x_List, n_] := TakeWhile[Rest[x], # < n/First[x] &]; |
|||
q = Rest /@ |
|||
NestWhileList[reduceList[#, n] &, primes, Length@# > 2 &]; |
|||
semiPrimes = Sort@Flatten@MapThread[Times, {q, primes[[;; Length@q]]}]; |
|||
Partition[TakeWhile[semiPrimes, # < 1000 &], UpTo[10]] // TableForm</lang> |
|||
{{out}}<pre> |
|||
15 21 33 35 39 51 55 57 65 69 |
|||
77 85 87 91 93 95 111 115 119 123 |
|||
129 133 141 143 145 155 159 161 177 183 |
|||
185 187 201 203 205 209 213 215 217 219 |
|||
221 235 237 247 249 253 259 265 267 287 |
|||
291 295 299 301 303 305 309 319 321 323 |
|||
327 329 335 339 341 355 365 371 377 381 |
|||
391 393 395 403 407 411 413 415 417 427 |
|||
437 445 447 451 453 469 471 473 481 485 |
|||
489 493 497 501 505 511 515 517 519 527 |
|||
533 535 537 543 545 551 553 559 565 573 |
|||
579 581 583 589 591 597 611 623 629 633 |
|||
635 649 655 667 669 671 679 681 685 687 |
|||
689 695 697 699 703 707 713 717 721 723 |
|||
731 737 745 749 753 755 763 767 771 779 |
|||
781 785 789 791 793 799 803 807 813 815 |
|||
817 831 835 843 849 851 865 869 871 879 |
|||
889 893 895 899 901 905 913 917 921 923 |
|||
933 939 943 949 951 955 959 965 973 979 |
|||
985 989 993 995 |
|||
</pre> |
</pre> |
||
=={{header|Ksh}}== |
=={{header|Ksh}}== |
||
< |
<syntaxhighlight lang="ksh">#!/bin/ksh |
||
# Odd squarefree semiprimes |
# Odd squarefree semiprimes |
||
Line 637: | Line 817: | ||
print ${osfsp[*]} |
print ${osfsp[*]} |
||
echo |
echo |
||
print "Counted ${#osfsp[*]} odd squarefree semiprimes under 1000"</ |
print "Counted ${#osfsp[*]} odd squarefree semiprimes under 1000"</syntaxhighlight> |
||
{{out}}<pre>15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 |
{{out}}<pre>15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 |
||
145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 |
145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 |
||
Line 650: | Line 830: | ||
Counted 194 odd squarefree semiprimes under 1000 |
Counted 194 odd squarefree semiprimes under 1000 |
||
</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">n = 1000; primes = Most@NestWhileList[NextPrime, 3, # < n/3 &]; |
|||
reduceList[x_List, n_] := TakeWhile[Rest[x], # < n/First[x] &]; |
|||
q = Rest /@ |
|||
NestWhileList[reduceList[#, n] &, primes, Length@# > 2 &]; |
|||
semiPrimes = Sort@Flatten@MapThread[Times, {q, primes[[;; Length@q]]}]; |
|||
Partition[TakeWhile[semiPrimes, # < 1000 &], UpTo[10]] // TableForm</syntaxhighlight> |
|||
{{out}}<pre> |
|||
15 21 33 35 39 51 55 57 65 69 |
|||
77 85 87 91 93 95 111 115 119 123 |
|||
129 133 141 143 145 155 159 161 177 183 |
|||
185 187 201 203 205 209 213 215 217 219 |
|||
221 235 237 247 249 253 259 265 267 287 |
|||
291 295 299 301 303 305 309 319 321 323 |
|||
327 329 335 339 341 355 365 371 377 381 |
|||
391 393 395 403 407 411 413 415 417 427 |
|||
437 445 447 451 453 469 471 473 481 485 |
|||
489 493 497 501 505 511 515 517 519 527 |
|||
533 535 537 543 545 551 553 559 565 573 |
|||
579 581 583 589 591 597 611 623 629 633 |
|||
635 649 655 667 669 671 679 681 685 687 |
|||
689 695 697 699 703 707 713 717 721 723 |
|||
731 737 745 749 753 755 763 767 771 779 |
|||
781 785 789 791 793 799 803 807 813 815 |
|||
817 831 835 843 849 851 865 869 871 879 |
|||
889 893 895 899 901 905 913 917 921 923 |
|||
933 939 943 949 951 955 959 965 973 979 |
|||
985 989 993 995 |
|||
</pre> |
|||
=={{header|Maxima}}== |
|||
<syntaxhighlight lang="maxima"> |
|||
block( |
|||
[count:0,oddsemiprime:[]], |
|||
while count<1000 do ( |
|||
i:lambda([x],oddp(x) and length(ifactors(x))=2 and unique(map(second,ifactors(x)))=[1])(count), |
|||
if i then oddsemiprime:endcons(count,oddsemiprime), |
|||
count:count+1), |
|||
oddsemiprime); |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[15,21,33,35,39,51,55,57,65,69,77,85,87,91,93,95,111,115,119,123,129,133,141,143,145,155,159,161,177,183,185,187,201,203,205,209,213,215,217,219,221,235,237,247,249,253,259,265,267,287,291,295,299,301,303,305,309,319,321,323,327,329,335,339,341,355,365,371,377,381,391,393,395,403,407,411,413,415,417,427,437,445,447,451,453,469,471,473,481,485,489,493,497,501,505,511,515,517,519,527,533,535,537,543,545,551,553,559,565,573,579,581,583,589,591,597,611,623,629,633,635,649,655,667,669,671,679,681,685,687,689,695,697,699,703,707,713,717,721,723,731,737,745,749,753,755,763,767,771,779,781,785,789,791,793,799,803,807,813,815,817,831,835,843,849,851,865,869,871,879,889,893,895,899,901,905,913,917,921,923,933,939,943,949,951,955,959,965,973,979,985,989,993,995] |
|||
</pre> |
</pre> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import algorithm, strutils, sugar |
||
const |
const |
||
Line 684: | Line 910: | ||
for i, n in result: |
for i, n in result: |
||
stdout.write ($n).align(3), if (i + 1) mod 20 == 0: '\n' else: ' ' |
stdout.write ($n).align(3), if (i + 1) mod 20 == 0: '\n' else: ' ' |
||
echo()</ |
echo()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 699: | Line 925: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">for(s=3, 999, f=factor(s); m=matsize(f); if(s%2==1&&m[1]==2&&f[1,2]==1&&f[2,2]==1, print(s)))</syntaxhighlight> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Odd_squarefree_semiprimes |
use strict; # https://rosettacode.org/wiki/Odd_squarefree_semiprimes |
||
Line 709: | Line 935: | ||
my (@primes, @found) = grep $_ & 1 && (1 x $_) !~ /^(11+)\1+$/, 3 .. 999 / 3; |
my (@primes, @found) = grep $_ & 1 && (1 x $_) !~ /^(11+)\1+$/, 3 .. 999 / 3; |
||
"@primes" =~ /\b(\d+)\b.*?\b(\d+)\b(?{ $found[$1 * $2] = $1 * $2 })(*FAIL)/; |
"@primes" =~ /\b(\d+)\b.*?\b(\d+)\b(?{ $found[$1 * $2] = $1 * $2 })(*FAIL)/; |
||
print "@{[ grep $_, @found[3 .. 999] ]}\n" =~ s/.{75}\K /\n/gr;</ |
print "@{[ grep $_, @found[3 .. 999] ]}\n" =~ s/.{75}\K /\n/gr;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 725: | Line 951: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">oss</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">oss</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> |
||
Line 733: | Line 959: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Found %d odd square-free semiprimes less than 1,000:\n %s\n"</span><span style="color: #0000FF;">,</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Found %d odd square-free semiprimes less than 1,000:\n %s\n"</span><span style="color: #0000FF;">,</span> |
||
<span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span> |
<span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 739: | Line 965: | ||
15, 21, 33, 35, 39, ..., 979, 985, 989, 993, 995 |
15, 21, 33, 35, 39, ..., 979, 985, 989, 993, 995 |
||
</pre> |
</pre> |
||
=={{header|Prolog}}== |
|||
works with swi-prolog |
|||
<syntaxhighlight lang="prolog"> |
|||
oddPrimes(3, Limit):- 3 =< Limit. |
|||
oddPrimes(N, Limit):- |
|||
between(5, Limit, N), |
|||
N /\ 1 > 0, % odd |
|||
N mod 3 > 0, % \= 3*i |
|||
M is floor(sqrt(N)) + 1, % reverse 6*I-1 |
|||
Max is M div 6, |
|||
forall(between(1, Max, I), (N mod (6*I-1) > 0, N mod (6*I+1) > 0)). |
|||
merge([], Sort, Sort). |
|||
merge([X|Sort1], [Y|Sort2], [X|Sort]):- |
|||
X < Y,!, |
|||
merge(Sort1, [Y|Sort2], Sort). |
|||
merge(Sort1, [Y|Sort2], [Y|Sort]):- |
|||
merge(Sort2, Sort1, Sort). |
|||
semiPrimes(PList, Limit, SpList):- |
|||
semiPrimes(PList, Limit, [], SpList). |
|||
semiPrimes([], _, Acc, Acc). % odd, squarefree generator |
|||
semiPrimes([P|PList], Limit, Acc, SpList):- |
|||
findall(Sp, (member(X, PList), X =< Limit div P, Sp is P * X), MList), |
|||
MList = [_|_],!, |
|||
merge(Acc, MList, Acc1), |
|||
semiPrimes(PList, Limit, Acc1, SpList). |
|||
semiPrimes(_, _, Acc, Acc). |
|||
showList(List):- |
|||
findnsols(20, X, (member(X, List), writef('%4r', [X])), _SubList), nl, |
|||
fail. |
|||
showList(_). |
|||
do:-Limit is 1000, |
|||
PLimit is Limit div 3, |
|||
findall(N, oddPrimes(N, PLimit), PList), |
|||
semiPrimes(PList, Limit, SpList),!, |
|||
showList(SpList). |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
?- time(do). |
|||
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
|||
129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 |
|||
221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 |
|||
327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 |
|||
437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 |
|||
533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 |
|||
635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 |
|||
731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 |
|||
817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 |
|||
933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
|||
% 11,306 inferences, 0.005 CPU in 0.006 seconds (85% CPU, 2410378 Lips) |
|||
true. |
|||
</pre> |
|||
=={{header|Python}}== |
|||
<syntaxhighlight lang="python">#!/usr/bin/python |
|||
def isPrime(n): |
|||
for i in range(2, int(n**0.5) + 1): |
|||
if n % i == 0: |
|||
return False |
|||
return True |
|||
if __name__ == '__main__': |
|||
for p in range(3, 999): |
|||
if not isPrime(p): |
|||
continue |
|||
for q in range(p+1, 1000//p): |
|||
if not isPrime(q): |
|||
continue |
|||
print(p*q, end = " ");</syntaxhighlight> |
|||
=={{header|Quackery}}== |
|||
<code>isprime</code> is defined at [[Primality by trial division#Quackery]]. |
|||
<syntaxhighlight lang="Quackery"> [ stack ] is limit |
|||
[ [] swap |
|||
[] temp put |
|||
dup limit put |
|||
3 / times |
|||
[ i^ isprime if |
|||
[ i^ join ] ] |
|||
behead drop |
|||
dup witheach |
|||
[ over i^ split drop |
|||
witheach |
|||
[ over * dup |
|||
limit share < iff |
|||
[ temp take |
|||
join |
|||
temp put ] |
|||
else |
|||
[ drop |
|||
conclude ] ] |
|||
drop ] |
|||
drop |
|||
limit release |
|||
temp take ] is task ( n --> list ) |
|||
1000 task sort echo</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[ 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 ]</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>say (3..333).grep(*.is-prime).combinations(2)».map( * * * ).flat\ |
||
.grep( * < 1000 ).sort.batch(20)».fmt('%3d').join: "\n";</ |
.grep( * < 1000 ).sort.batch(20)».fmt('%3d').join: "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
<pre> 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
||
Line 756: | Line 1,093: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm finds odd squarefree semiprimes (product of 2 primes) that are less then N. */ |
||
parse arg hi cols . /*obtain optional argument from the CL.*/ |
parse arg hi cols . /*obtain optional argument from the CL.*/ |
||
if hi=='' | hi=="," then hi= 1000 /* " " " " " " */ |
if hi=='' | hi=="," then hi= 1000 /* " " " " " " */ |
||
Line 802: | Line 1,139: | ||
end /*k*/ /* [↑] only process numbers ≤ √ J */ |
end /*k*/ /* [↑] only process numbers ≤ √ J */ |
||
#= #+1; @.#= j; sq.#= j*j /*bump # Ps; assign next P; P squared*/ |
#= #+1; @.#= j; sq.#= j*j /*bump # Ps; assign next P; P squared*/ |
||
end /*j*/; return</ |
end /*j*/; return</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 833: | Line 1,170: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring">load "stdlib.ring" # for isprime() function |
||
? "working..." + nl + "Odd squarefree semiprimes are:" |
? "working..." + nl + "Odd squarefree semiprimes are:" |
||
Line 870: | Line 1,207: | ||
s = string(x) l = len(s) |
s = string(x) l = len(s) |
||
if l > y y = l ok |
if l > y y = l ok |
||
return substr(" ", 11 - y + l) + s</ |
return substr(" ", 11 - y + l) + s</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>working... |
<pre>working... |
||
Line 887: | Line 1,224: | ||
Found 194 Odd squarefree semiprimes. |
Found 194 Odd squarefree semiprimes. |
||
done... |
done... |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{{works with|HP|49}} |
|||
≪ → max |
|||
≪ { } 3 |
|||
'''DO''' |
|||
3 1 CF |
|||
'''WHILE''' DUP2 > 1 FC? AND '''REPEAT''' |
|||
DUP2 * |
|||
'''IF''' DUP max ≤ '''THEN''' 4 ROLL + UNROT '''ELSE''' DROP 1 SF '''END''' |
|||
NEXTPRIME |
|||
'''END''' |
|||
DROP NEXTPRIME |
|||
'''UNTIL''' DUP 3 * max > '''END''' |
|||
DROP SORT |
|||
≫ ≫ '<span style="color:blue">OSSP</span>' STO |
|||
1000 <span style="color:blue">OSSP</span> |
|||
{{out}} |
|||
<pre> |
|||
1: {15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995} |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
<syntaxhighlight lang="ruby"> |
|||
require 'prime' |
|||
res = (1..1000).step(2).select {|n| n.prime_division.map(&:last) == [1, 1] } |
|||
res.each_slice(20){|slice| puts "%4d"*slice.size % slice} |
|||
puts "\nCount: #{res.count}"</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
|||
129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 |
|||
221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 |
|||
327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 |
|||
437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 |
|||
533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 |
|||
635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 |
|||
731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 |
|||
817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 |
|||
933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
|||
Count: 194 |
|||
</pre> |
|||
=={{header|Scala}}== |
|||
Scala3 ready |
|||
<syntaxhighlight lang="scala"> |
|||
val primes3 = 3 #:: LazyList.from(5, 6) |
|||
.flatMap(p => Iterator(p, p + 2)) |
|||
.filter(p => (5 to math.sqrt(p).floor.toInt by 6).forall(a => p % a > 0 && p % (a + 2) > 0)) |
|||
def merge(sort1: Seq[Int], sort2: Seq[Int]): Seq[Int] = { |
|||
def iter(sort1: Seq[Int], sort2: Seq[Int], acc: Seq[Int]): Seq[Int] = { |
|||
if (sort1.isEmpty) return acc ++ sort2 |
|||
val (x, y) = (sort1.head, sort2.head) |
|||
val (min, s1, s2) = if (x < y) (x, sort1.tail, sort2) |
|||
else (y, sort2.tail, sort1) |
|||
iter(s1, s2, acc :+ min) |
|||
} |
|||
iter(sort1, sort2, Seq()) |
|||
} |
|||
def semiPrimes(limit: Int): Seq[Int] = { // odd, squarefree generator |
|||
def iter(primeList: Seq[Int], acc: Seq[Int]): Seq[Int] = { |
|||
val (start, primeList1) = (primeList.head, primeList.tail) |
|||
val subList = primeList1.map(_ * start).takeWhile(_ <= limit) |
|||
if (subList.isEmpty) return acc |
|||
iter(primeList1, merge(acc, subList)) |
|||
} |
|||
iter(primes3, Seq()) |
|||
} |
|||
@main def main = { |
|||
val start = System.currentTimeMillis |
|||
val spList = semiPrimes(1000) |
|||
val duration = System.currentTimeMillis - start |
|||
spList.grouped(20).foreach(group => |
|||
group.foreach(sp => print(f"$sp%3d ")) |
|||
println |
|||
) |
|||
println(s"number: ${spList.length} [time elapsed: $duration ms]") |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 |
|||
129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 |
|||
221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 |
|||
327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 |
|||
437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 |
|||
533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 |
|||
635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 |
|||
731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 |
|||
817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 |
|||
933 939 943 949 951 955 959 965 973 979 985 989 993 995 |
|||
number: 194 [time elapsed: 6 ms] |
|||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func odd_squarefree_almost_primes(upto, k=2) { |
||
k.squarefree_almost_primes(upto).grep{.is_odd} |
k.squarefree_almost_primes(upto).grep{.is_odd} |
||
} |
} |
||
Line 898: | Line 1,332: | ||
say "Found #{list.len} odd square-free semiprimes <= #{n.commify}:" |
say "Found #{list.len} odd square-free semiprimes <= #{n.commify}:" |
||
say (list.first(10).join(', '), ', ..., ', list.last(10).join(', ')) |
say (list.first(10).join(', '), ', ..., ', list.last(10).join(', ')) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 907: | Line 1,341: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-seq}} |
|||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
<syntaxhighlight lang="wren">import "./math" for Int |
|||
{{libheader|Wren-sort}} |
|||
import "./fmt" for Fmt |
|||
import "/seq" for Lst |
|||
import "/fmt" for Fmt |
|||
import "/sort" for Sort |
|||
var primes = Int.primeSieve(333) |
var primes = Int.primeSieve(333) |
||
Line 924: | Line 1,354: | ||
} |
} |
||
} |
} |
||
Sort.quick(oss) |
|||
System.print("Odd squarefree semiprimes under 1,000:") |
System.print("Odd squarefree semiprimes under 1,000:") |
||
Fmt.tprint("$3d", oss.sort(), 10) |
|||
for (chunk in Lst.chunks(oss, 10)) Fmt.print("$3d", chunk) |
|||
System.print("\n%(oss.count) such numbers found.")</ |
System.print("\n%(oss.count) such numbers found.")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 957: | Line 1,386: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is a prime number |
||
int N, I; |
int N, I; |
||
[if N <= 1 then return false; |
[if N <= 1 then return false; |
||
Line 986: | Line 1,415: | ||
Text(0, " odd squarefree semiprimes found below 1000. |
Text(0, " odd squarefree semiprimes found below 1000. |
||
"); |
"); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 21:58, 17 May 2024
- Task
Odd numbers of the form p*q where p and q are distinct primes, where p*q < 1000
- See also
11l
F odd_square_free_semiprime(=n)
I n % 2 == 0
R 0B
V count = 0
V i = 3
L i * i <= n
L n % i == 0
I ++count > 1
R 0B
n I/= i
i += 2
R count == 1
print(‘Odd square-free semiprimes < 1000:’)
V count = 0
L(i) (1.<1000).step(2)
I odd_square_free_semiprime(i)
print(‘#4’.format(i), end' ‘’)
I ++count % 20 == 0
print()
print("\nCount: "count)
- Output:
Odd square-free semiprimes < 1000: 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 Count: 194
Action!
INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit
INCLUDE "H6:SIEVE.ACT"
PROC Main()
DEFINE MAX="999"
BYTE ARRAY primes(MAX+1)
INT i,j,count,max2,limit
INT ARRAY res(300)
Put(125) PutE() ;clear the screen
Sieve(primes,MAX+1)
count=0 max2=MAX/2
FOR i=3 TO max2
DO
IF primes(i) THEN
limit=MAX/i
FOR j=i+1 TO limit
DO
IF primes(j) THEN
res(count)=i*j
count==+1
FI
OD
FI
OD
SortI(res,count,0)
FOR i=0 TO count-1
DO
PrintI(res(i)) Put(32)
OD
PrintF("%E%EThere are %I odd numbers",count)
RETURN
- Output:
Screenshot from Atari 8-bit computer
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 There are 194 odd numbers
ALGOL 68
BEGIN # find some odd square free semi-primes #
# numbers of the form p*q where p =/= q and p, q are prime #
# reurns a list of primes up to n #
PROC prime list = ( INT n )[]INT:
BEGIN
# sieve the primes to n #
INT no = 0, yes = 1;
[ 1 : n ]INT p;
p[ 1 ] := no; p[ 2 ] := yes;
FOR i FROM 3 BY 2 TO n DO p[ i ] := yes OD;
FOR i FROM 4 BY 2 TO n DO p[ i ] := no OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO
IF p[ i ] = yes THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := no OD FI
OD;
# replace the sieve with a list #
INT p pos := 0;
FOR i TO n DO IF p[ i ] = yes THEN p[ p pos +:= 1 ] := i FI OD;
p[ 1 : p pos ]
END # prime list # ;
# show odd square free semi-primes up to 1000 #
INT max number = 1000;
INT max prime = 1 + ( max number OVER 3 ); # the smallest odd prime is 3, so this shuld be enough primes #
[]INT prime = prime list( max prime );
[ 1 : max number ]BOOL numbers; FOR i TO max number DO numbers[ i ] := FALSE OD;
FOR i FROM 2 TO UPB prime - 1 DO
FOR j FROM i + 1 TO UPB prime
WHILE INT pq = prime[ i ] * prime[ j ];
pq < max number
DO
numbers[ pq ] := TRUE
OD
OD;
INT n count := 0;
FOR i TO max number DO
IF numbers[ i ] THEN
print( ( " ", whole( i, -4 ) ) );
n count +:= 1;
IF n count MOD 20 = 0 THEN print( ( newline ) ) FI
FI
OD
END
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
Arturo
primes: select 0..1000 => prime?
lst: sort unique flatten map primes 'p [
map select primes 'q -> all? @[odd? p*q p<>q 1000>p*q]=>[p*&]
]
loop split.every:10 lst 'a ->
print map a => [pad to :string & 4]
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
AWK
# syntax: GAWK -f ODD_SQUAREFREE_SEMIPRIMES.AWK
# converted from C++
BEGIN {
start = 1
stop = 999
for (i=start; i<=stop; i+=2) {
if (is_odd_square_free_semiprime(i)) {
printf("%4d%1s",i,++count%10?"":"\n")
}
}
printf("\nOdd Square Free Semiprimes %d-%d: %d\n",start,stop,count)
exit(0)
}
function is_odd_square_free_semiprime(n, count,i) {
if (and(n,1) == 0) {
return(0)
}
for (i=3; i*i<=n; i+=2) {
for (; n%i==0; n=int(n/i)) {
if (++count > 1) {
return(0)
}
}
}
return(count==1)
}
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 Odd Square Free Semiprimes 1-999: 194
BASIC
FreeBASIC
Use the function from Primality by trial division#FreeBASIC as an include. This code generates the odd squarefree semiprimes in ascending order of their first factor, then their second.
#include "isprime.bas"
dim as integer p, q
for p = 3 to 999
if not isprime(p) then continue for
for q = p+1 to 1000\p
if not isprime(q) then continue for
print p*q;" ";
next q
next p
- Output:
15 21 33 39 51 57 69 87 93 111 123 129 141 159 177 183 201 213 219 237 249 267 291 303 309 321 327 339 381 393 411 417 447 453 471 489 501 519 537 543 573 579 591 597 633 669 681 687 699 717 723 753 771 789 807 813 831 843 849 879 921 933 939 951 993 35 55 65 85 95 115 145 155 185 205 215 235 265 295 305 335 355 365 395 415 445 485 505 515 535 545 565 635 655 685 695 745 755 785 815 835 865 895 905 955 965 985 995 77 91 119 133 161 203 217 259 287 301 329 371 413 427 469 497 511 553 581 623 679 707 721 749 763 791 889 917 959 973 143 187 209 253 319 341 407 451 473 517 583 649 671 737 781 803 869 913 979 221 247 299 377 403 481 533 559 611 689 767 793 871 923 949 323 391 493 527 629 697 731 799 901 437 551 589 703 779 817 893 667 713 851 943 989 899
Tiny BASIC
LET P = 1
10 LET P = P + 2
LET Q = P
IF P >= 1000 THEN END
LET A = P
GOSUB 100
IF Z = 0 THEN GOTO 10
20 LET Q = Q + 2
IF Q > 1000/P THEN GOTO 10
LET A = Q
GOSUB 100
IF Z = 0 THEN GOTO 20
PRINT P," ",Q," ",P*Q
GOTO 20
100 REM PRIMALITY BY TRIAL DIVISION
LET Z = 1
LET I = 2
110 IF (A/I)*I = A THEN LET Z = 0
IF Z = 0 THEN RETURN
LET I = I + 1
IF I*I <= A THEN GOTO 110
RETURN
C#
This reveals a set of semi-prime numbers (with exactly two factors for each n), where 1 < p < q < n. It is square-free, since p < q.
using System; using static System.Console; using System.Collections;
using System.Linq; using System.Collections.Generic;
class Program { static void Main(string[] args) {
int lmt = 1000, amt, c = 0, sr = (int)Math.Sqrt(lmt), lm2; var res = new List<int>();
var pr = PG.Primes(lmt / 3 + 5).ToArray(); lm2 = pr.OrderBy(i => Math.Abs(sr - i)).First();
lm2 = Array.IndexOf(pr, lm2); for (var p = 0; p < lm2; p++) { amt = 0; for (var q = p + 1; amt < lmt; q++)
res.Add(amt = pr[p] * pr[q]); } res.Sort(); foreach(var item in res.TakeWhile(x => x < lmt))
Write("{0,4} {1}", item, ++c % 20 == 0 ? "\n" : "");
Write("\n\nCounted {0} odd squarefree semiprimes under {1}", c, lmt); } }
class PG { public static IEnumerable<int> Primes(int lim) {
var flags = new bool[lim + 1]; int j = 3;
for (int d = 8, sq = 9; sq <= lim; j += 2, sq += d += 8)
if (!flags[j]) { yield return j;
for (int k = sq, i = j << 1; k <= lim; k += i) flags[k] = true; }
for (; j <= lim; j += 2) if (!flags[j]) yield return j; } }
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 Counted 194 odd squarefree semiprimes under 1000
C++
#include <iomanip>
#include <iostream>
bool odd_square_free_semiprime(int n) {
if ((n & 1) == 0)
return false;
int count = 0;
for (int i = 3; i * i <= n; i += 2) {
for (; n % i == 0; n /= i) {
if (++count > 1)
return false;
}
}
return count == 1;
}
int main() {
const int n = 1000;
std::cout << "Odd square-free semiprimes < " << n << ":\n";
int count = 0;
for (int i = 1; i < n; i += 2) {
if (odd_square_free_semiprime(i)) {
++count;
std::cout << std::setw(4) << i;
if (count % 20 == 0)
std::cout << '\n';
}
}
std::cout << "\nCount: " << count << '\n';
return 0;
}
- Output:
Odd square-free semiprimes < 1000: 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 Count: 194
Delphi
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
function CustomSort (Item1, Item2: Pointer): Integer;
begin
Result:=integer(Item1)-integer(Item2);
end;
procedure OddSquareFreeSemiprimes(Memo: TMemo);
var P,Q,I: integer;
const Limit = 1000;
var LS: TList;
var S: string;
begin
LS:=TList.Create;
try
P:=1;
{Test all relevant combinations of P and Q}
for P:=1 to Limit div 5 do
begin
if ((P and 1)=0) or (not IsPrime(P)) then continue;
for Q:=P+2 to Limit div P do
begin
if ((Q and 1)=0) or (not IsPrime(Q)) then continue;
{Put in list}
LS.Add(Pointer(P*Q))
end;
end;
{List is not in order, so sort it}
LS.Sort(CustomSort);
S:='';
for I:=0 to LS.Count-1 do
begin
S:=S+Format('%8D',[Integer(LS[I])]);
If (I mod 5)=4 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count='+IntToStr(LS.Count));
finally LS.Free; end;
end;
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 Count=194 Elapsed Time: 9.048 ms.
EasyLang
func oddsemi n .
i = 3
while i <= sqrt n
while n mod i = 0
count += 1
if count > 1
return 0
.
n = n div i
.
i += 2
.
return if count = 1
.
for i = 1 step 2 to 999
if oddsemi i = 1
write i & " "
.
.
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
F#
This task uses Extensible Prime Generator (F#)
// Odd squarefree semiprimes. Nigel Galloway: January 4th., 2023
let n=primes32()|>Seq.skip 1|>Seq.takeWhile((>)333)|>List.ofSeq
List.allPairs n n|>Seq.filter(fun(n,g)->n<g)|>Seq.map(fun(n,g)->n*g)|>Seq.filter((>)1000)|>Seq.iter(printf "%d "); printfn ""
- Output:
15 21 33 39 51 57 69 87 93 111 123 129 141 159 177 183 201 213 219 237 249 267 291 303 309 321 327 339 381 393 411 417 447 453 471 489 501 519 537 543 573 579 591 597 633 669 681 687 699 717 723 753 771 789 807 813 831 843 849 879 921 933 939 951 993 35 55 65 85 95 115 145 155 185 205 215 235 265 295 305 335 355 365 395 415 445 485 505 515 535 545 565 635 655 685 695 745 755 785 815 835 865 895 905 955 965 985 995 77 91 119 133 161 203 217 259 287 301 329 371 413 427 469 497 511 553 581 623 679 707 721 749 763 791 889 917 959 973 143 187 209 253 319 341 407 451 473 517 583 649 671 737 781 803 869 913 979 221 247 299 377 403 481 533 559 611 689 767 793 871 923 949 323 391 493 527 629 697 731 799 901 437 551 589 703 779 817 893 667 713 851 943 989 899
Factor
USING: combinators.short-circuit formatting grouping io kernel
math.primes.factors math.ranges prettyprint sequences sets ;
: sq-free-semiprime? ( n -- ? )
factors { [ length 2 = ] [ all-unique? ] } 1&& ;
: odd-sfs-upto ( n -- seq )
1 swap 2 <range> [ sq-free-semiprime? ] filter ;
999 odd-sfs-upto dup length
"Found %d odd square-free semiprimes < 1000:\n" printf
20 group [ [ "%4d" printf ] each nl ] each nl
- Output:
Found 194 odd square-free semiprimes < 1000: 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
Forth
: odd-square-free-semi-prime? { n -- ? }
n 1 and 0= if false exit then
0 { count }
3
begin
dup dup * n <=
while
begin
dup n swap mod 0=
while
count 1+ to count
count 1 > if
drop false exit
then
dup n swap / to n
repeat
2 +
repeat
drop
count 1 = ;
: special_odd_numbers ( n -- )
." Odd square-free semiprimes < " dup 1 .r ." :" cr
0 swap
1 do
i odd-square-free-semi-prime? if
1+
i 4 .r
dup 20 mod 0= if cr then
then
2 +loop
cr ." Count: " . cr ;
1000 special_odd_numbers
bye
- Output:
Odd square-free semiprimes < 1000: 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 Count: 194
Go
package main
import (
"fmt"
"rcu"
"sort"
)
func main() {
primes := rcu.Primes(333)
var oss []int
for i := 1; i < len(primes)-1; i++ {
for j := i + 1; j < len(primes); j++ {
n := primes[i] * primes[j]
if n >= 1000 {
break
}
oss = append(oss, n)
}
}
sort.Ints(oss)
fmt.Println("Odd squarefree semiprimes under 1,000:")
for i, n := range oss {
fmt.Printf("%3d ", n)
if (i+1)%10 == 0 {
fmt.Println()
}
}
fmt.Printf("\n\n%d such numbers found.\n", len(oss))
}
- Output:
Odd squarefree semiprimes under 1,000: 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 194 such numbers found.
J
require'stats'
(#~ 1000>])*/"1 p:1+2 comb p:inv 1000%3
15 21 33 39 51 57 69 87 93 111 123 129 141 159 177 183 201 213 219 237 249 267 291 303 309 321 327 339 381 393 411 417 447 453 471 489 501 519 537 543 573 579 591 597 633 669 681 687 699 717 723 753 771 789 807 813 831 843 849 879 921 933 939 951 993 35 55 65 85 95 115 145 155 185 205 215 235 265 295 305 335 355 365 395 415 445 485 505 515 535 545 565 635 655 685 695 745 755 785 815 835 865 895 905 955 965 985 995 77 91 119 133 161 203 217 259 287 301 329 371 413 427 469 497 511 553 581 623 679 707 721 749 763 791 889 917 959 973 143 187 209 253 319 341 407 451 473 517 583 649 671 737 781 803 869 913 979 221 247 299 377 403 481 533 559 611 689 767 793 871 923 949 323 391 493 527 629 697 731 799 901 437 551 589 703 779 817 893 667 713 851 943 989 899
Note that these values are sorted in order of their smallest prime factor followed by the larger prime factor. In other words, since 899 is 29*31, and there's 8 odd primes smaller than 29, there are (conceptually speaking) 9 ascending subsequences of semiprimes here.
jq
Works with gojq, the Go implementation of jq
See e.g. Erdős-primes#jq for a suitable definition of `is_prime`.
# Output: a stream of proper square-free odd prime factors of .
def proper_odd_squarefree_prime_factors:
range(3; 1 + sqrt|floor) as $i
| select( (. % $i) == 0 )
| (. / $i) as $r
| select($i != $r and all($i, $r; is_prime) )
| $i, $r;
def is_odd_squarefree_semiprime:
isempty(proper_odd_squarefree_prime_factors) | not;
# For pretty-printing
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
# The task:
[range(3;1000;2)
| select(is_odd_squarefree_semiprime)]
| nwise(10)
| map(lpad(3)) | join(" ")
- Output:
Julia
using Primes
twoprimeproduct(n) = (a = factor(n).pe; length(a) == 2 && all(p -> p[2] == 1, a))
special1k = filter(n -> isodd(n) && twoprimeproduct(n), 1:1000)
foreach(p -> print(rpad(p[2], 4), p[1] % 20 == 0 ? "\n" : ""), enumerate(special1k))
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
Ksh
#!/bin/ksh
# Odd squarefree semiprimes
# # Odd numbers of the form p*q where p and q are distinct primes and p*q<1000
# # Variables:
#
integer i j candidate cnt=0
typeset -a primes osfsp
# # Functions:
#
# # Function _isprime(n) return 1 for prime, 0 for not prime
#
function _isprime {
typeset _n ; integer _n=$1
typeset _i ; integer _i
(( _n < 2 )) && return 0
for (( _i=2 ; _i*_i<=_n ; _i++ )); do
(( ! ( _n % _i ) )) && return 0
done
return 1
}
# # Function _firstNprimes(n, arr) return array of first N primes
#
function _firstNprimes {
typeset _n ; integer _n=$1
typeset _arr ; nameref _arr="$2"
typeset _i _cnt ; integer _i=1 _cnt=0
while (( _cnt <= _n )); do
_isprime ${_i} ; (( $? )) && (( _cnt++ )) && _arr+=( ${_i} )
(( _i++ ))
done
}
# # Function _isunique(n, arr) add n to array if unique to array
#
function _isunique {
typeset _n ; integer _n=$1
typeset _arr ; nameref _arr="$2"
typeset _buff _oldIFS
_oldIFS=$IFS
IFS=\|
_buff=${_arr[*]}
[[ ${_n} == @(${_buff}) ]] || _arr+=( ${_n} )
IFS=${_oldIFS}
}
# # Function _insertionSort(array) - Insersion sort of array of integers
#
function _insertionSort {
typeset _arr ; nameref _arr="$1"
typeset _i _j _val ; integer _i _j _val
for (( _i=1; _i<${#_arr[*]}; _i++ )); do
_val=${_arr[_i]}
(( _j = _i - 1 ))
while (( _j>=0 && _arr[_j]>_val )); do
_arr[_j+1]=${_arr[_j]}
(( _j-- ))
done
_arr[_j+1]=${_val}
done
}
######
# main #
######
_firstNprimes 66 primes # 67th prime -> 337 * 3 = 1011 > 999
for ((i=0; i<${#primes[*]}; i++)); do
for ((j=0; j<${#primes[*]}; j++)); do
((j == i )) && continue
(( candidate = primes[i] * primes[j] ))
(( candidate > 999 )) || (( ! $(( candidate & 1 )) )) && continue
_isunique ${candidate} osfsp
done
done
_insertionSort osfsp
print ${osfsp[*]}
echo
print "Counted ${#osfsp[*]} odd squarefree semiprimes under 1000"
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
Counted 194 odd squarefree semiprimes under 1000
Mathematica / Wolfram Language
n = 1000; primes = Most@NestWhileList[NextPrime, 3, # < n/3 &];
reduceList[x_List, n_] := TakeWhile[Rest[x], # < n/First[x] &];
q = Rest /@
NestWhileList[reduceList[#, n] &, primes, Length@# > 2 &];
semiPrimes = Sort@Flatten@MapThread[Times, {q, primes[[;; Length@q]]}];
Partition[TakeWhile[semiPrimes, # < 1000 &], UpTo[10]] // TableForm
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
Maxima
block(
[count:0,oddsemiprime:[]],
while count<1000 do (
i:lambda([x],oddp(x) and length(ifactors(x))=2 and unique(map(second,ifactors(x)))=[1])(count),
if i then oddsemiprime:endcons(count,oddsemiprime),
count:count+1),
oddsemiprime);
- Output:
[15,21,33,35,39,51,55,57,65,69,77,85,87,91,93,95,111,115,119,123,129,133,141,143,145,155,159,161,177,183,185,187,201,203,205,209,213,215,217,219,221,235,237,247,249,253,259,265,267,287,291,295,299,301,303,305,309,319,321,323,327,329,335,339,341,355,365,371,377,381,391,393,395,403,407,411,413,415,417,427,437,445,447,451,453,469,471,473,481,485,489,493,497,501,505,511,515,517,519,527,533,535,537,543,545,551,553,559,565,573,579,581,583,589,591,597,611,623,629,633,635,649,655,667,669,671,679,681,685,687,689,695,697,699,703,707,713,717,721,723,731,737,745,749,753,755,763,767,771,779,781,785,789,791,793,799,803,807,813,815,817,831,835,843,849,851,865,869,871,879,889,893,895,899,901,905,913,917,921,923,933,939,943,949,951,955,959,965,973,979,985,989,993,995]
Nim
import algorithm, strutils, sugar
const
M = 1000 - 1
N = M div 3 # Minimal value for "p" is 3.
# Sieve of Eratosthenes.
var composite: array[3..N, bool]
for n in countup(3, N, 2):
let n2 = n * n
if n2 > N: break
if not composite[n]:
for k in countup(n2, N, 2 * n):
composite[k] = true
let primes = collect(newSeq):
for n in countup(3, N, 2):
if not composite[n]: n
var result: seq[int]
for i in 0..<primes.high:
let p = primes[i]
for j in (i+1)..primes.high:
let q = primes[j]
if p * q > M: break
result.add p * q
result.sort()
for i, n in result:
stdout.write ($n).align(3), if (i + 1) mod 20 == 0: '\n' else: ' '
echo()
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
PARI/GP
for(s=3, 999, f=factor(s); m=matsize(f); if(s%2==1&&m[1]==2&&f[1,2]==1&&f[2,2]==1, print(s)))
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Odd_squarefree_semiprimes
use warnings;
my (@primes, @found) = grep $_ & 1 && (1 x $_) !~ /^(11+)\1+$/, 3 .. 999 / 3;
"@primes" =~ /\b(\d+)\b.*?\b(\d+)\b(?{ $found[$1 * $2] = $1 * $2 })(*FAIL)/;
print "@{[ grep $_, @found[3 .. 999] ]}\n" =~ s/.{75}\K /\n/gr;
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
Phix
function oss(integer n) sequence f = prime_factors(n,true) return length(f)==2 and f[1]!=f[2] end function sequence res = apply(true,sprintf,{{"%d"},filter(tagset(999,1,2),oss)}) printf(1,"Found %d odd square-free semiprimes less than 1,000:\n %s\n", {length(res),join(shorten(res,"",5),", ")})
- Output:
Found 194 odd square-free semiprimes less than 1,000: 15, 21, 33, 35, 39, ..., 979, 985, 989, 993, 995
Prolog
works with swi-prolog
oddPrimes(3, Limit):- 3 =< Limit.
oddPrimes(N, Limit):-
between(5, Limit, N),
N /\ 1 > 0, % odd
N mod 3 > 0, % \= 3*i
M is floor(sqrt(N)) + 1, % reverse 6*I-1
Max is M div 6,
forall(between(1, Max, I), (N mod (6*I-1) > 0, N mod (6*I+1) > 0)).
merge([], Sort, Sort).
merge([X|Sort1], [Y|Sort2], [X|Sort]):-
X < Y,!,
merge(Sort1, [Y|Sort2], Sort).
merge(Sort1, [Y|Sort2], [Y|Sort]):-
merge(Sort2, Sort1, Sort).
semiPrimes(PList, Limit, SpList):-
semiPrimes(PList, Limit, [], SpList).
semiPrimes([], _, Acc, Acc). % odd, squarefree generator
semiPrimes([P|PList], Limit, Acc, SpList):-
findall(Sp, (member(X, PList), X =< Limit div P, Sp is P * X), MList),
MList = [_|_],!,
merge(Acc, MList, Acc1),
semiPrimes(PList, Limit, Acc1, SpList).
semiPrimes(_, _, Acc, Acc).
showList(List):-
findnsols(20, X, (member(X, List), writef('%4r', [X])), _SubList), nl,
fail.
showList(_).
do:-Limit is 1000,
PLimit is Limit div 3,
findall(N, oddPrimes(N, PLimit), PList),
semiPrimes(PList, Limit, SpList),!,
showList(SpList).
- Output:
?- time(do). 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 % 11,306 inferences, 0.005 CPU in 0.006 seconds (85% CPU, 2410378 Lips) true.
Python
#!/usr/bin/python
def isPrime(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
if __name__ == '__main__':
for p in range(3, 999):
if not isPrime(p):
continue
for q in range(p+1, 1000//p):
if not isPrime(q):
continue
print(p*q, end = " ");
Quackery
isprime
is defined at Primality by trial division#Quackery.
[ stack ] is limit
[ [] swap
[] temp put
dup limit put
3 / times
[ i^ isprime if
[ i^ join ] ]
behead drop
dup witheach
[ over i^ split drop
witheach
[ over * dup
limit share < iff
[ temp take
join
temp put ]
else
[ drop
conclude ] ]
drop ]
drop
limit release
temp take ] is task ( n --> list )
1000 task sort echo
- Output:
[ 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 ]
Raku
say (3..333).grep(*.is-prime).combinations(2)».map( * * * ).flat\
.grep( * < 1000 ).sort.batch(20)».fmt('%3d').join: "\n";
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995
REXX
/*REXX pgm finds odd squarefree semiprimes (product of 2 primes) that are less then N. */
parse arg hi cols . /*obtain optional argument from the CL.*/
if hi=='' | hi=="," then hi= 1000 /* " " " " " " */
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
call genP /*build array of semaphores for primes.*/
w= 10 /*width of a number in any column. */
@oss= ' odd squarefree semiprimes < ' commas(1000)
if cols>0 then say ' index │'center(@oss, 1 + cols*(w+1) )
if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
idx= 1 /*initialize the index of output lines.*/
$=; ss.= 0 /*a list of odd squarefree semiprimes. */
do j=2 while @.j < hi /*gen odd squarefree semiprimes < HI.*/
do k=j+1 while @.k < hi; _= @.j*@.k /*ensure primes are squarefree & < HI.*/
if _>=hi then leave /*Is the product ≥ HI? Then skip it. */
ss._= 1 /*mark # as being squarefree semiprime.*/
end /*k*/
end /*j*/
oss= 0 /*number of odd squarefree semiprimes. */
do m=3 by 2 to hi-1 /*search a list of possible candicates.*/
if \ss.m then iterate /*Does this number exist? No, skip it.*/
oss= oss + 1 /*bump count of odd sq─free semiprimes.*/
if cols==0 then iterate /*Build the list (to be shown later)? */
$= $ right( commas(m), w) /*add an odd square─free semiprime. */
if oss//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*m*/
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─')
say
say 'Found ' commas(oss) @oss
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define low primes; # of primes so far*/
#= 5; sq.#= @.# ** 2 /*the highest prime squared (so far). */
/* [↓] generate more primes ≤ high.*/
do j=@.#+2 by 2 to hi+1 /*find odd primes from here on. */
parse var j '' -1 _; if _==5 then iterate /*J ÷ by 5? (right digit).*/
if j//3==0 then iterate; if j//7==0 then iterate /*" " " 3? J ÷ by 7? */
do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/
if j//@.k==0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; sq.#= j*j /*bump # Ps; assign next P; P squared*/
end /*j*/; return
- output when using the default inputs:
index │ odd squarefree semiprimes < 1,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 15 21 33 35 39 51 55 57 65 69 11 │ 77 85 87 91 93 95 111 115 119 123 21 │ 129 133 141 143 145 155 159 161 177 183 31 │ 185 187 201 203 205 209 213 215 217 219 41 │ 221 235 237 247 249 253 259 265 267 287 51 │ 291 295 299 301 303 305 309 319 321 323 61 │ 327 329 335 339 341 355 365 371 377 381 71 │ 391 393 395 403 407 411 413 415 417 427 81 │ 437 445 447 451 453 469 471 473 481 485 91 │ 489 493 497 501 505 511 515 517 519 527 101 │ 533 535 537 543 545 551 553 559 565 573 111 │ 579 581 583 589 591 597 611 623 629 633 121 │ 635 649 655 667 669 671 679 681 685 687 131 │ 689 695 697 699 703 707 713 717 721 723 141 │ 731 737 745 749 753 755 763 767 771 779 151 │ 781 785 789 791 793 799 803 807 813 815 161 │ 817 831 835 843 849 851 865 869 871 879 171 │ 889 893 895 899 901 905 913 917 921 923 181 │ 933 939 943 949 951 955 959 965 973 979 191 │ 985 989 993 995 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 194 odd squarefree semiprimes < 1,000
Ring
load "stdlib.ring" # for isprime() function
? "working..." + nl + "Odd squarefree semiprimes are:"
limit = 1000 Prim = []
# create table of prime numbers from 3 to 1000 / 3
pr = []
for n = 3 to 1000 / 3
if isprime(n) Add(pr,n) ok
next pl = len(pr)
# calculate upper limit for n
for nlim = 1 to pl
if pr[nlim] * pr[nlim] > limit exit ok
next nlim--
# add items to result list and sort
for n = 1 to nlim
for m = n + 1 to pl
amt = pr[n] * pr[m]
if amt > limit exit ok
add(Prim, amt)
next
next Prim = sort(Prim)
# display results
for n = 1 to len(Prim)
see sf(Prim[n], 4) + " "
if n % 20 = 0 see nl ok
next n--
? nl + nl + "Found " + n + " Odd squarefree semiprimes." + nl + "done..."
# a very plain string formatter, intended to even up columnar outputs
def sf x, y
s = string(x) l = len(s)
if l > y y = l ok
return substr(" ", 11 - y + l) + s
- Output:
working... Odd squarefree semiprimes are: 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 Found 194 Odd squarefree semiprimes. done...
RPL
≪ → max
≪ { } 3
DO
3 1 CF
WHILE DUP2 > 1 FC? AND REPEAT
DUP2 *
IF DUP max ≤ THEN 4 ROLL + UNROT ELSE DROP 1 SF END
NEXTPRIME
END
DROP NEXTPRIME
UNTIL DUP 3 * max > END
DROP SORT
≫ ≫ 'OSSP' STO
1000 OSSP
- Output:
1: {15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995}
Ruby
require 'prime'
res = (1..1000).step(2).select {|n| n.prime_division.map(&:last) == [1, 1] }
res.each_slice(20){|slice| puts "%4d"*slice.size % slice}
puts "\nCount: #{res.count}"
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 Count: 194
Scala
Scala3 ready
val primes3 = 3 #:: LazyList.from(5, 6)
.flatMap(p => Iterator(p, p + 2))
.filter(p => (5 to math.sqrt(p).floor.toInt by 6).forall(a => p % a > 0 && p % (a + 2) > 0))
def merge(sort1: Seq[Int], sort2: Seq[Int]): Seq[Int] = {
def iter(sort1: Seq[Int], sort2: Seq[Int], acc: Seq[Int]): Seq[Int] = {
if (sort1.isEmpty) return acc ++ sort2
val (x, y) = (sort1.head, sort2.head)
val (min, s1, s2) = if (x < y) (x, sort1.tail, sort2)
else (y, sort2.tail, sort1)
iter(s1, s2, acc :+ min)
}
iter(sort1, sort2, Seq())
}
def semiPrimes(limit: Int): Seq[Int] = { // odd, squarefree generator
def iter(primeList: Seq[Int], acc: Seq[Int]): Seq[Int] = {
val (start, primeList1) = (primeList.head, primeList.tail)
val subList = primeList1.map(_ * start).takeWhile(_ <= limit)
if (subList.isEmpty) return acc
iter(primeList1, merge(acc, subList))
}
iter(primes3, Seq())
}
@main def main = {
val start = System.currentTimeMillis
val spList = semiPrimes(1000)
val duration = System.currentTimeMillis - start
spList.grouped(20).foreach(group =>
group.foreach(sp => print(f"$sp%3d "))
println
)
println(s"number: ${spList.length} [time elapsed: $duration ms]")
}
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 number: 194 [time elapsed: 6 ms]
Sidef
func odd_squarefree_almost_primes(upto, k=2) {
k.squarefree_almost_primes(upto).grep{.is_odd}
}
with (1e3) {|n|
var list = odd_squarefree_almost_primes(n, 2)
say "Found #{list.len} odd square-free semiprimes <= #{n.commify}:"
say (list.first(10).join(', '), ', ..., ', list.last(10).join(', '))
}
- Output:
Found 194 odd square-free semiprimes <= 1,000: 15, 21, 33, 35, 39, 51, 55, 57, 65, 69, ..., 951, 955, 959, 965, 973, 979, 985, 989, 993, 995
Wren
import "./math" for Int
import "./fmt" for Fmt
var primes = Int.primeSieve(333)
var oss = []
for (i in 1...primes.count-1) {
for (j in i + 1...primes.count) {
var n = primes[i] * primes[j]
if (n >= 1000) break
oss.add(n)
}
}
System.print("Odd squarefree semiprimes under 1,000:")
Fmt.tprint("$3d", oss.sort(), 10)
System.print("\n%(oss.count) such numbers found.")
- Output:
Odd squarefree semiprimes under 1,000: 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 194 such numbers found.
XPL0
func IsPrime(N); \Return 'true' if N is a prime number
int N, I;
[if N <= 1 then return false;
for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true;
];
def Max = 1000;
int N, A(Max), P, Q, Count;
[for N:= 0 to Max-1 do
A(N):= false;
for P:= 3 to Max/5 do
if IsPrime(P) then
for Q:= P+2 to Max/P do
if IsPrime(Q) then
if P*Q < Max then
A(P*Q):= true;
Count:= 0;
for N:= 0 to Max-1 do
if A(N) then
[IntOut(0, N);
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
];
CrLf(0);
IntOut(0, Count);
Text(0, " odd squarefree semiprimes found below 1000.
");
]
- Output:
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123 129 133 141 143 145 155 159 161 177 183 185 187 201 203 205 209 213 215 217 219 221 235 237 247 249 253 259 265 267 287 291 295 299 301 303 305 309 319 321 323 327 329 335 339 341 355 365 371 377 381 391 393 395 403 407 411 413 415 417 427 437 445 447 451 453 469 471 473 481 485 489 493 497 501 505 511 515 517 519 527 533 535 537 543 545 551 553 559 565 573 579 581 583 589 591 597 611 623 629 633 635 649 655 667 669 671 679 681 685 687 689 695 697 699 703 707 713 717 721 723 731 737 745 749 753 755 763 767 771 779 781 785 789 791 793 799 803 807 813 815 817 831 835 843 849 851 865 869 871 879 889 893 895 899 901 905 913 917 921 923 933 939 943 949 951 955 959 965 973 979 985 989 993 995 194 odd squarefree semiprimes found below 1000.
- Draft Programming Tasks
- Prime Numbers
- 11l
- Action!
- Action! Tool Kit
- Action! Sieve of Eratosthenes
- ALGOL 68
- Arturo
- AWK
- BASIC
- FreeBASIC
- Tiny BASIC
- C sharp
- C++
- Delphi
- SysUtils,StdCtrls
- EasyLang
- F Sharp
- Factor
- Forth
- Go
- Go-rcu
- J
- Jq
- Julia
- Ksh
- Mathematica
- Wolfram Language
- Maxima
- Nim
- PARI/GP
- Perl
- Phix
- Prolog
- Python
- Quackery
- Raku
- REXX
- Ring
- RPL
- Ruby
- Scala
- Sidef
- Wren
- Wren-math
- Wren-fmt
- XPL0