Odd squarefree semiprimes: Difference between revisions
m (→{{header|FreeBASIC}}: -fix) |
(add parigp) |
||
| Line 264: | Line 264: | ||
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> |
</pre> |
||
=={{header|PARI/GP}}== |
|||
<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)))</lang> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Revision as of 13:19, 4 April 2021
- Task
Odd numbers of the form p*q where p and q are distinct primes, where p*q < 1000
ALGOL 68
<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 #
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</lang>
- 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
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.
<lang freebasic>#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</lang>
- 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
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. <lang csharp>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; } }</lang>
- 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++
<lang cpp>#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;
}</lang>
- 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
Factor
<lang 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</lang>
- 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
<lang 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</lang>
- 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
Julia
<lang 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))
</lang>
- 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
<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)))</lang>
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
Raku
<lang perl6>say (3..333).grep(*.is-prime).combinations(2)».map( * * * ).flat\
.grep( * < 1000 ).sort.batch(20)».fmt('%3d').join: "\n";</lang>
- 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
<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 /* " " " " " " */ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */
@sss= ' odd squarefree semiprimes < ' commas(1000)
if cols>0 then say ' index │'center(@sss, 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 /*ensure primes are squarefree & < HI.*/
_= @.j * @.k /*calculate the product of 2 odd primes*/
if _>=hi then leave /*Is the product ≥ HI? Then skip it. */
ss._= 1 /*mark # as being squarefree semiprime.*/
end /*k*/
end /*j*/
sss= 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.*/
sss= sss + 1 /*bump count of odd sq─free semiprimes.*/
if cols==0 then iterate /*Build the list (to be shown later)? */
c= commas(m) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add odd sq─free semiprime, allow big#*/
if sss//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.*/ say say 'Found ' commas(sss) @sss 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; @.6= 13 /*define some low primes. */
#=6; s.#= @.# **2 /*number of primes so far; prime²*/
/* [↓] generate more primes ≤ high.*/
do j=@.#+4 by 2 to hi+1 /*find odd primes from here on. */
parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
if j//11==0 then iterate /*" " " 11? */
/* [↑] the above four lines saves time*/
do k=6 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.#= j*j /*bump # Ps; assign next P; P squared*/
end /*j*/; return</lang>
- 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
<lang 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</lang>
- 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...
Wren
<lang ecmascript>import "/math" for Int import "/seq" for Lst import "/fmt" for Fmt import "/sort" for Sort
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)
}
} Sort.quick(oss) System.print("Odd squarefree semiprimes under 1,000:") for (chunk in Lst.chunks(oss, 10)) Fmt.print("$3d", chunk) System.print("\n%(oss.count) such numbers found.")</lang>
- 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.