Rosetta Code

Odd squarefree semiprimes: Difference between revisions

Page Discussion

Odd squarefree semiprimes (view source)

Revision as of 09:13, 8 January 2024

26,313 bytes added ,  4 months ago
→‎{{header|Wren}}: Tidied
(Added Go)
(30 intermediate revisions by 19 users not shown)
Line 4:
;Task:
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>
 
=={{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!}}==
{{libheader|Action! Tool Kit}}
{{libheader|Action! Sieve of Eratosthenes}}
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Odd_squarefree_semiprimes.png Screenshot from Atari 8-bit computer]
<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
 
There are 194 odd numbers
</pre>
 
=={{header|ALGOL 68}}==
<langsyntaxhighlight lang="algol68">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 #
Line 47 ⟶ 143:
FI
OD
END</langsyntaxhighlight>
{{out}}
<pre>
Line 61 ⟶ 157:
933 939 943 949 951 955 959 965 973 979 985 989 993 995
</pre>
 
=={{header|Arturo}}==
 
<langsyntaxhighlight lang="rebol">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]</langsyntaxhighlight>
 
{{out}}
Line 94 ⟶ 191:
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
<lang AWK>
# syntax: GAWK -f ODD_SQUAREFREE_SEMIPRIMES.AWK
# converted from C++
Line 121 ⟶ 218:
return(count==1)
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 152 ⟶ 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.
 
<langsyntaxhighlight lang="freebasic">#include "isprime.bas"
dim as integer p, q
for p = 3 to 999
Line 160 ⟶ 257:
print p*q;" ";
next q
next p</langsyntaxhighlight>
{{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}}===
<langsyntaxhighlight lang="tinybasic"> LET P = 1
10 LET P = P + 2
LET Q = P
Line 185 ⟶ 282:
LET I = I + 1
IF I*I <= A THEN GOTO 110
RETURN</langsyntaxhighlight>
 
=={{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>'''.
<langsyntaxhighlight lang="csharp">using System; using static System.Console; using System.Collections;
using System.Linq; using System.Collections.Generic;
 
Line 205 ⟶ 302:
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; } }</langsyntaxhighlight>
{{out}}
<pre> 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123
Line 221 ⟶ 318:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
 
Line 251 ⟶ 348:
std::cout << "\nCount: " << count << '\n';
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 269 ⟶ 366:
</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|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>
=={{header|Factor}}==
{{works with|Factor|0.99 2021-02-05}}
<langsyntaxhighlight lang="factor">USING: combinators.short-circuit formatting grouping io kernel
math.primes.factors math.ranges prettyprint sequences sets ;
 
Line 282 ⟶ 507:
999 odd-sfs-upto dup length
"Found %d odd square-free semiprimes < 1000:\n" printf
20 group [ [ "%4d" printf ] each nl ] each nl</langsyntaxhighlight>
{{out}}
<pre>
Line 300 ⟶ 525:
=={{header|Forth}}==
{{works with|Gforth}}
<langsyntaxhighlight lang="forth">: odd-square-free-semi-prime? { n -- ? }
n 1 and 0= if false exit then
0 { count }
Line 334 ⟶ 559:
 
1000 special_odd_numbers
bye</langsyntaxhighlight>
 
{{out}}
Line 355 ⟶ 580:
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 384 ⟶ 609:
}
fmt.Printf("\n\n%d such numbers found.\n", len(oss))
}</langsyntaxhighlight>
 
{{out}}
Line 412 ⟶ 637:
194 such numbers found.
</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}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
 
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:
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(" ")</syntaxhighlight>
{{out}}
As for [[#Arturo|Arturo]], [[#Wren|Wren]], et al.
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
twoprimeproduct(n) = (a = factor(n).pe; length(a) == 2 && all(p -> p[2] == 1, a))
Line 421 ⟶ 686:
 
foreach(p -> print(rpad(p[2], 4), p[1] % 20 == 0 ? "\n" : ""), enumerate(special1k))
</langsyntaxhighlight>{{out}}
<pre>
15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123
Line 433 ⟶ 698:
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|Ksh}}==
<syntaxhighlight lang="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"</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
 
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>
 
=={{header|Nim}}==
<langsyntaxhighlight Nimlang="nim">import algorithm, strutils, sugar
 
const
Line 467 ⟶ 882:
for i, n in result:
stdout.write ($n).align(3), if (i + 1) mod 20 == 0: '\n' else: ' '
echo()</langsyntaxhighlight>
 
{{out}}
Line 482 ⟶ 897:
 
=={{header|PARI/GP}}==
<langsyntaxhighlight 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)))</langsyntaxhighlight>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Odd_squarefree_semiprimes
Line 492 ⟶ 907:
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;</langsyntaxhighlight>
{{out}}
<pre>
Line 508 ⟶ 923:
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="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: #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 516 ⟶ 931:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 522 ⟶ 937:
15, 21, 33, 35, 39, ..., 979, 985, 989, 993, 995
</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}}==
<syntaxhighlight lang="raku" perl6line>say (3..333).grep(*.is-prime).combinations(2)».map( * * * ).flat\
.grep( * < 1000 ).sort.batch(20)».fmt('%3d').join: "\n";</langsyntaxhighlight>
{{out}}
<pre> 15 21 33 35 39 51 55 57 65 69 77 85 87 91 93 95 111 115 119 123
Line 539 ⟶ 1,065:
 
=={{header|REXX}}==
<langsyntaxhighlight 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.*/
if hi=='' | hi=="," then hi= 1000 /* " " " " " " */
Line 575 ⟶ 1,101:
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; #= 5 /*define low primes; # of primes so far*/
#= 5; ssq.#= @.# ** 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 if _==5 then iterate /*J divisible÷ by 5? (right digdigit).*/
if j//3==0 then iterate; if j// 37==0 then iterate /*" " " 3? J ÷ by 7? */
do k=5 while sq.k<=j if j// 7==0 then iterate /*" " " 7? [↓] divide by the known odd primes.*/
do k=5 while s.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; s sq.#= j*j /*bump # Ps; assign next P; P squared*/
end /*j*/; return</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 617 ⟶ 1,142:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">load "stdlib.ring" # for isprime() function
? "working..." + nl + "Odd squarefree semiprimes are:"
Line 654 ⟶ 1,179:
s = string(x) l = len(s)
if l > y y = l ok
return substr(" ", 11 - y + l) + s</langsyntaxhighlight>
{{out}}
<pre>working...
Line 671 ⟶ 1,196:
Found 194 Odd squarefree semiprimes.
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>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">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(', '))
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./math" for Int
{{libheader|Wren-sort}}
<lang ecmascript>import "./mathfmt" for IntFmt
import "/seq" for Lst
import "/fmt" for Fmt
import "/sort" for Sort
 
var primes = Int.primeSieve(333)
Line 692 ⟶ 1,326:
}
}
Sort.quick(oss)
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.")</langsyntaxhighlight>
 
{{out}}
Line 722 ⟶ 1,355:
 
194 such numbers found.
</pre>
 
=={{header|XPL0}}==
<syntaxhighlight lang="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.
");
]</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
194 odd squarefree semiprimes found below 1000.
</pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/310733...354712"