Rosetta Code

Special odd numbers: Difference between revisions

Page Discussion

Special odd numbers (view source)

Revision as of 14:06, 3 April 2021

18,565 bytes removed ,  3 years ago
m
Link to new page
(Added Algol 68)
m (Link to new page)
 
(4 intermediate revisions by 2 users not shown)
Line 1:
Task moved to [[Odd squarefree semiprimes]] one.
{{Draft task}}
[[Category:Prime Numbers]]
 
;Task:
Odd numbers of the form p*q where p and q are distinct primes, where '''p*q < 1000'''
<br><br>
 
=={{header|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 prime = prime list( 100 * max number ); # (very) rough approximation of where the last prime under 1001 is #
[ 1 : max number ]BOOL numbers; FOR i TO max number DO numbers[ i ] := FALSE OD;
FOR i FROM 2 TO max number - 1 DO
FOR j FROM i + 1 TO max number
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>
{{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|C#|CSharp}}==
This reveals a set of non-prime numbers with exactly two factors for each '''<big>''n''</big>''', where '''<big>''1 < p < q < n''</big>'''.
<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} special odd prime products 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>
{{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 special odd prime products under 1000</pre>
 
=={{header|Factor}}==
{{works with|Factor|0.99 2021-02-05}}
<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>
{{out}}
<pre>
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
</pre>
 
=={{header|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>{{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|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>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
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
</pre>
 
=={{header|Ring}}==
<lang ring>? "working..." + nl + "Special odd numbers are:"
limit = 1000
Prim = []
 
# table of prime numbers from 3 to 1000/3
pr = [ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331]
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)
if Prim[n] < 100
see " "
ok
see " " + Prim[n] + " "
if n % 20 = 0
see nl
ok
next
n--
? nl + "Found " + n + " Special odd numbers." + nl + "done..."</lang>
{{out}}
<pre>working...
Special odd numbers 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 Special odd numbers.
done...</pre>
 
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
{{libheader|Wren-sort}}
<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>
 
{{out}}
<pre>
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.
</pre>
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/310702...310707"