Special odd numbers: Difference between revisions
Content added Content deleted
(Added C++ solution) |
m (Link to new page) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 1: | 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|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> |
|||
{{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|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= 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> |
Latest revision as of 14:06, 3 April 2021
Task moved to Odd squarefree semiprimes one.