Sequence of primes by trial division: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: use true/false explicitly) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 1: | Line 1: | ||
{{task|Prime Numbers}} |
{{task|Prime Numbers}} |
||
Line 32: | Line 30: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F prime(a) |
||
R !(a < 2 | any((2 .. Int(a ^ 0.5)).map(x -> @a % x == 0))) |
R !(a < 2 | any((2 .. Int(a ^ 0.5)).map(x -> @a % x == 0))) |
||
Line 38: | Line 36: | ||
R (0 .< n).filter(i -> prime(i)) |
R (0 .< n).filter(i -> prime(i)) |
||
print(primes_below(100))</ |
print(primes_below(100))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 46: | Line 44: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">BYTE FUNC IsPrime(CARD a) |
||
CARD i |
CARD i |
||
Line 83: | Line 81: | ||
PrintF("Primes in range [%U..%U]:%E",begin,end) |
PrintF("Primes in range [%U..%U]:%E",begin,end) |
||
PrintPrimes(begin,end) |
PrintPrimes(begin,end) |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Sequence_of_primes_by_trial_division.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Sequence_of_primes_by_trial_division.png Screenshot from Atari 8-bit computer] |
||
Line 101: | Line 99: | ||
Use the generic function Prime_Numbers.Is_Prime, as specified in [[Prime decomposition#Ada]]. The program reads two numbers A and B from the command line and prints all primes between A and B (inclusive). |
Use the generic function Prime_Numbers.Is_Prime, as specified in [[Prime decomposition#Ada]]. The program reads two numbers A and B from the command line and prints all primes between A and B (inclusive). |
||
< |
<syntaxhighlight lang="ada">with Prime_Numbers, Ada.Text_IO, Ada.Command_Line; |
||
procedure Sequence_Of_Primes is |
procedure Sequence_Of_Primes is |
||
Line 118: | Line 116: | ||
end if; |
end if; |
||
end loop; |
end loop; |
||
end Sequence_Of_Primes;</ |
end Sequence_Of_Primes;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 126: | Line 124: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Simple bounded sequence using the "is prime" routine from [[Primality by trial division#ALGOL 68]] |
Simple bounded sequence using the "is prime" routine from [[Primality by trial division#ALGOL 68]] |
||
< |
<syntaxhighlight lang="algol68"># is prime PROC from the primality by trial division task # |
||
MODE ISPRIMEINT = INT; |
MODE ISPRIMEINT = INT; |
||
PROC is prime = ( ISPRIMEINT p )BOOL: |
PROC is prime = ( ISPRIMEINT p )BOOL: |
||
Line 159: | Line 157: | ||
print( ( " ", whole( primes[ p ], 0 ) ) ) |
print( ( " ", whole( primes[ p ], 0 ) ) ) |
||
OD; |
OD; |
||
print( ( newline ) )</ |
print( ( newline ) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 167: | Line 165: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
Uses the ALGOL W isPrime procedure from the Primality by Trial Division task. |
Uses the ALGOL W isPrime procedure from the Primality by Trial Division task. |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% use the isPrime procedure from the Primality by Trial Division task % |
% use the isPrime procedure from the Primality by Trial Division task % |
||
logical procedure isPrime ( integer value n ) ; algol "isPrime" ; |
logical procedure isPrime ( integer value n ) ; algol "isPrime" ; |
||
Line 198: | Line 196: | ||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 210: | Line 208: | ||
=={{header|ALGOL-M}}== |
=={{header|ALGOL-M}}== |
||
The approach here follows an example given by Edsger Dijkstra in his classic 1969 paper, Notes on Structured Programming. Only odd numbers above 2 are checked for primality, and only the prime numbers previously found (up to the square root of the number under examination) are tested as divisors. |
The approach here follows an example given by Edsger Dijkstra in his classic 1969 paper, Notes on Structured Programming. Only odd numbers above 2 are checked for primality, and only the prime numbers previously found (up to the square root of the number under examination) are tested as divisors. |
||
< |
<syntaxhighlight lang="algol"> |
||
BEGIN |
BEGIN |
||
Line 260: | Line 258: | ||
END |
END |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 280: | Line 278: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">getPrimes: function [upto][ |
||
result: new [2] |
result: new [2] |
||
loop range.step:2 3 upto 'x [ |
loop range.step:2 3 upto 'x [ |
||
Line 294: | Line 292: | ||
] |
] |
||
print getPrimes 100</ |
print getPrimes 100</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 302: | Line 300: | ||
=={{header|AsciiDots}}== |
=={{header|AsciiDots}}== |
||
Program to generate all prime numbers up to the input (inclusive). This implementation is very inefficient currently since the primality test checks every number from 2 to N rather than checking up to the square root, excluding even numbers from the factor checks, etc. |
Program to generate all prime numbers up to the input (inclusive). This implementation is very inefficient currently since the primality test checks every number from 2 to N rather than checking up to the square root, excluding even numbers from the factor checks, etc. |
||
<syntaxhighlight lang="asciidots"> |
|||
<lang AsciiDots> |
|||
``warps |
``warps |
||
%$ABCPR |
%$ABCPR |
||
Line 340: | Line 338: | ||
//| \#0/ | |
//| \#0/ | |
||
\{*}-------/ |
\{*}-------/ |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 349: | Line 347: | ||
=={{header|ATS}}== |
=={{header|ATS}}== |
||
<syntaxhighlight lang="ats">(* |
|||
<lang ATS>(* |
|||
// Lazy-evaluation: |
// Lazy-evaluation: |
||
// sieve for primes |
// sieve for primes |
||
Line 418: | Line 416: | ||
end // end of [main0] |
end // end of [main0] |
||
(* ****** ****** *)</ |
(* ****** ****** *)</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f SEQUENCE_OF_PRIMES_BY_TRIAL_DIVISION.AWK |
# syntax: GAWK -f SEQUENCE_OF_PRIMES_BY_TRIAL_DIVISION.AWK |
||
BEGIN { |
BEGIN { |
||
Line 446: | Line 444: | ||
return(1) |
return(1) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 454: | Line 452: | ||
=={{header|BASIC256}}== |
=={{header|BASIC256}}== |
||
< |
<syntaxhighlight lang="freebasic">function isPrime(v) |
||
if v < 2 then return False |
if v < 2 then return False |
||
if v mod 2 = 0 then return v = 2 |
if v mod 2 = 0 then return v = 2 |
||
Line 468: | Line 466: | ||
if isPrime(i) then print string(i); " "; |
if isPrime(i) then print string(i); " "; |
||
next i |
next i |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Igual que la entrada de FreeBASIC.</pre> |
<pre>Igual que la entrada de FreeBASIC.</pre> |
||
=={{header|Batch File}}== |
=={{header|Batch File}}== |
||
<syntaxhighlight lang="batch file"> |
|||
<lang Batch File> |
|||
@echo off |
@echo off |
||
::Prime list using trial division |
::Prime list using trial division |
||
Line 515: | Line 513: | ||
set lin=!cnt1:~-5!: |
set lin=!cnt1:~-5!: |
||
goto:eof |
goto:eof |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 553: | Line 551: | ||
Based on the test in the [[Primality_by_trial_division#Befunge|Primality by trial division]] task, this list all primes between 2 and 1,000,000. |
Based on the test in the [[Primality_by_trial_division#Befunge|Primality by trial division]] task, this list all primes between 2 and 1,000,000. |
||
< |
<syntaxhighlight lang="befunge">2>:::"}"8*:*>`#@_48*:**2v |
||
v_v#`\*:%*:*84\/*:*84::+< |
v_v#`\*:%*:*84\/*:*84::+< |
||
v#>::48*:*/\48*:*%%!#v_1^ |
v#>::48*:*/\48*:*%%!#v_1^ |
||
<^+1$_.#<5#<5#<+#<,#<<0:\</ |
<^+1$_.#<5#<5#<+#<,#<<0:\</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 576: | Line 574: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<syntaxhighlight lang="c"> |
|||
<lang C> |
|||
#include<stdio.h> |
#include<stdio.h> |
||
Line 611: | Line 609: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output : |
Output : |
||
<pre> |
<pre> |
||
Line 646: | Line 644: | ||
=={{header|C sharp}}== |
=={{header|C sharp}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 658: | Line 656: | ||
static IEnumerable<int> Primes(int limit) => Enumerable.Range(2, limit-1).Where(IsPrime); |
static IEnumerable<int> Primes(int limit) => Enumerable.Range(2, limit-1).Where(IsPrime); |
||
static bool IsPrime(int n) => Enumerable.Range(2, (int)Math.Sqrt(n)-1).All(i => n % i != 0); |
static bool IsPrime(int n) => Enumerable.Range(2, (int)Math.Sqrt(n)-1).All(i => n % i != 0); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 665: | Line 663: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <math.h> |
#include <math.h> |
||
#include <iostream> |
#include <iostream> |
||
Line 696: | Line 694: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 707: | Line 705: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="lisp">(ns test-p.core |
||
(:require [clojure.math.numeric-tower :as math])) |
(:require [clojure.math.numeric-tower :as math])) |
||
Line 725: | Line 723: | ||
a)) |
a)) |
||
(println (primes-below 100))</ |
(println (primes-below 100))</syntaxhighlight> |
||
{{Output}} |
{{Output}} |
||
Line 731: | Line 729: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun primes-up-to (max-number) |
||
"Compute all primes up to MAX-NUMBER using trial division" |
"Compute all primes up to MAX-NUMBER using trial division" |
||
(loop for n from 2 upto max-number |
(loop for n from 2 upto max-number |
||
Line 742: | Line 740: | ||
(lambda (x) (integerp (/ n x)))) |
(lambda (x) (integerp (/ n x)))) |
||
(print (primes-up-to 100))</ |
(print (primes-up-to 100))</syntaxhighlight> |
||
Output: <pre>(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</pre> |
Output: <pre>(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</pre> |
||
Line 748: | Line 746: | ||
=={{header|Crystal}}== |
=={{header|Crystal}}== |
||
See https://rosettacode.org/wiki/Primality_by_trial_division#Crystal |
See https://rosettacode.org/wiki/Primality_by_trial_division#Crystal |
||
< |
<syntaxhighlight lang="ruby">require "big" |
||
def primep5?(n) # P5 Prime Generator primality test |
def primep5?(n) # P5 Prime Generator primality test |
||
Line 766: | Line 764: | ||
# Create sequence of primes from 1_000_000_001 to 1_000_000_201 |
# Create sequence of primes from 1_000_000_001 to 1_000_000_201 |
||
n = 1_000_000_001; n.step(to: n+200, by: 2) { |p| puts p if primep5?(p) }</ |
n = 1_000_000_001; n.step(to: n+200, by: 2) { |p| puts p if primep5?(p) }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1000000007 |
<pre>1000000007 |
||
Line 782: | Line 780: | ||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
This is a quite inefficient prime generator. |
This is a quite inefficient prime generator. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.range, std.algorithm, std.traits, |
||
std.numeric, std.concurrency; |
std.numeric, std.concurrency; |
||
Line 804: | Line 802: | ||
.take(20) |
.take(20) |
||
.writeln; |
.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]</pre> |
<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]</pre> |
||
Line 813: | Line 811: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
===Trial division=== |
===Trial division=== |
||
< |
<syntaxhighlight lang="scheme">(lib 'sequences) |
||
(define (is-prime? p) |
(define (is-prime? p) |
||
(cond |
(cond |
||
Line 821: | Line 819: | ||
(for/and ((d [3 5 .. (1+ (sqrt p))] )) (!zero? (modulo p d)))])) |
(for/and ((d [3 5 .. (1+ (sqrt p))] )) (!zero? (modulo p d)))])) |
||
(is-prime? 101) → #t </ |
(is-prime? 101) → #t </syntaxhighlight> |
||
===Bounded - List filter === |
===Bounded - List filter === |
||
< |
<syntaxhighlight lang="scheme">(filter is-prime? (range 1 100)) |
||
→ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</ |
→ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</syntaxhighlight> |
||
=== Unbounded - Sequence filter === |
=== Unbounded - Sequence filter === |
||
< |
<syntaxhighlight lang="scheme">(define f-primes (filter is-prime? [2 .. ])) |
||
→ # 👓 filter: #sequence [2 3 .. Infinity[ |
→ # 👓 filter: #sequence [2 3 .. Infinity[ |
||
(take f-primes 25) |
(take f-primes 25) |
||
→ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</ |
→ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</syntaxhighlight> |
||
=== Unbounded - Stream === |
=== Unbounded - Stream === |
||
< |
<syntaxhighlight lang="scheme">(define (s-next-prime n) ;; n odd |
||
(for ((p [n (+ n 2) .. ] )) |
(for ((p [n (+ n 2) .. ] )) |
||
#:break (is-prime? p) => (cons p (+ p 2)))) |
#:break (is-prime? p) => (cons p (+ p 2)))) |
||
Line 843: | Line 841: | ||
(take s-primes 25) |
(take s-primes 25) |
||
→ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</ |
→ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</syntaxhighlight> |
||
=== Unbounded - Generator === |
=== Unbounded - Generator === |
||
< |
<syntaxhighlight lang="scheme">(define (g-next-prime n) |
||
(define next |
(define next |
||
(for ((p [n .. ] )) #:break (is-prime? p) => p )) |
(for ((p [n .. ] )) #:break (is-prime? p) => p )) |
||
Line 855: | Line 853: | ||
(take g-primes 25) |
(take g-primes 25) |
||
→ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</ |
→ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)</syntaxhighlight> |
||
=== Unbounded - Background task === |
=== Unbounded - Background task === |
||
< |
<syntaxhighlight lang="scheme">(lib 'tasks) |
||
(lib 'bigint) |
(lib 'bigint) |
||
Line 879: | Line 877: | ||
1000000000121 |
1000000000121 |
||
1000000000163 |
1000000000163 |
||
*stopped*</ |
*stopped*</syntaxhighlight> |
||
=={{header|EDSAC order code}}== |
=={{header|EDSAC order code}}== |
||
Line 887: | Line 885: | ||
In the program as posted, the list of possible divisors holds 30 primes, from 5 to 131. The program finds primes less than 131^2 = 17161, the largest being 17159. Assuming 650 orders per second, this would have taken the original EDSAC about an hour. |
In the program as posted, the list of possible divisors holds 30 primes, from 5 to 131. The program finds primes less than 131^2 = 17161, the largest being 17159. Assuming 650 orders per second, this would have taken the original EDSAC about an hour. |
||
< |
<syntaxhighlight lang="edsac"> |
||
[List of primes by trial division, for Rosetta Code website.] |
[List of primes by trial division, for Rosetta Code website.] |
||
[EDSAC program, Initial Orders 2.] |
[EDSAC program, Initial Orders 2.] |
||
Line 1,050: | Line 1,048: | ||
E25Z [define entry point] |
E25Z [define entry point] |
||
PF [acc = 0 on entry] |
PF [acc = 0 on entry] |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,071: | Line 1,069: | ||
=={{header|Eiffel}}== |
=={{header|Eiffel}}== |
||
<syntaxhighlight lang="eiffel"> |
|||
<lang Eiffel> |
|||
class |
class |
||
APPLICATION |
APPLICATION |
||
Line 1,144: | Line 1,142: | ||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,160: | Line 1,158: | ||
=={{header|Elena}}== |
=={{header|Elena}}== |
||
ELENA 4.x : |
ELENA 4.x : |
||
< |
<syntaxhighlight lang="elena">import extensions; |
||
import system'routines; |
import system'routines; |
||
import system'math; |
import system'math; |
||
Line 1,173: | Line 1,171: | ||
{ |
{ |
||
console.printLine(Primes(100)) |
console.printLine(Primes(100)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,180: | Line 1,178: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule Prime do |
||
def sequence do |
def sequence do |
||
Stream.iterate(2, &(&1+1)) |> Stream.filter(&is_prime/1) |
Stream.iterate(2, &(&1+1)) |> Stream.filter(&is_prime/1) |
||
Line 1,194: | Line 1,192: | ||
end |
end |
||
IO.inspect Prime.sequence |> Enum.take(20)</ |
IO.inspect Prime.sequence |> Enum.take(20)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,202: | Line 1,200: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
<syntaxhighlight lang="erre"> |
|||
<lang ERRE> |
|||
PROGRAM PRIME_GENERATOR |
PROGRAM PRIME_GENERATOR |
||
Line 1,218: | Line 1,216: | ||
END LOOP |
END LOOP |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
You must press Ctrl+Break to stop the program. |
You must press Ctrl+Break to stop the program. |
||
{{out}} |
{{out}} |
||
Line 1,241: | Line 1,239: | ||
=={{header|F Sharp}}== |
=={{header|F Sharp}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
(* |
(* |
||
Nigel Galloway April 7th., 2017. |
Nigel Galloway April 7th., 2017. |
||
Line 1,250: | Line 1,248: | ||
yield n; yield! fg (Seq.cache(Seq.filter (fun g->g%n<>0) (Seq.skip 1 ng)))} |
yield n; yield! fg (Seq.cache(Seq.filter (fun g->g%n<>0) (Seq.skip 1 ng)))} |
||
fg (Seq.initInfinite(id)|>Seq.skip 2) |
fg (Seq.initInfinite(id)|>Seq.skip 2) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Let's print the sequence Prime[23] to Prime[42]. |
Let's print the sequence Prime[23] to Prime[42]. |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="fsharp"> |
||
[23..42] |> Seq.iter(fun n->printf "%d " (Seq.item n SofE)) |
[23..42] |> Seq.iter(fun n->printf "%d " (Seq.item n SofE)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 |
89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 |
||
Line 1,261: | Line 1,259: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: combinators kernel lists lists.lazy math math.functions |
||
math.ranges prettyprint sequences ; |
math.ranges prettyprint sequences ; |
||
Line 1,275: | Line 1,273: | ||
! Show the first fifteen primes. |
! Show the first fifteen primes. |
||
15 primes ltake list>array .</ |
15 primes ltake list>array .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,282: | Line 1,280: | ||
=={{header|FileMaker}}== |
=={{header|FileMaker}}== |
||
< |
<syntaxhighlight lang="filemaker"> |
||
#May 10th., 2018. |
#May 10th., 2018. |
||
Line 1,355: | Line 1,353: | ||
End If |
End If |
||
# |
# |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
This program stores the generated primes into a user allocated array and uses the primes generated so far to test divisibility of subsequent candidates. In FORTH, the PAD can be used as a large memory area that is always available, and the main .primes word makes use of that. |
This program stores the generated primes into a user allocated array and uses the primes generated so far to test divisibility of subsequent candidates. In FORTH, the PAD can be used as a large memory area that is always available, and the main .primes word makes use of that. |
||
<syntaxhighlight lang="forth"> |
|||
<lang Forth> |
|||
variable p-start \ beginning of prime buffer |
variable p-start \ beginning of prime buffer |
||
variable p-end \ end of prime buffer |
variable p-end \ end of prime buffer |
||
Line 1,399: | Line 1,397: | ||
i @ 5 .r |
i @ 5 .r |
||
cell +loop ; |
cell +loop ; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,435: | Line 1,433: | ||
This method avoids considering multiples of two and three, leading to the need to pre-load array PRIME and print the first few values explicitly rather than flounder about with special startup tricks. Even so, in order not to pre-load with 7, and to correctly start the factor testing with 5, the first few primes are found with some wasted effort because 5 is not needed at the start. Storing the primes as found has the obvious advantage of enabling divisions only by prime numbers, but care with the startup is needed to ensure that primes have indeed been stored before they are called for. |
This method avoids considering multiples of two and three, leading to the need to pre-load array PRIME and print the first few values explicitly rather than flounder about with special startup tricks. Even so, in order not to pre-load with 7, and to correctly start the factor testing with 5, the first few primes are found with some wasted effort because 5 is not needed at the start. Storing the primes as found has the obvious advantage of enabling divisions only by prime numbers, but care with the startup is needed to ensure that primes have indeed been stored before they are called for. |
||
<syntaxhighlight lang="fortran"> |
|||
<lang Fortran> |
|||
CONCOCTED BY R.N.MCLEAN, APPLIED MATHS COURSE, AUCKLAND UNIVERSITY, MCMLXXI. |
CONCOCTED BY R.N.MCLEAN, APPLIED MATHS COURSE, AUCKLAND UNIVERSITY, MCMLXXI. |
||
INTEGER ENUFF,PRIME(44) |
INTEGER ENUFF,PRIME(44) |
||
Line 1,480: | Line 1,478: | ||
40 IF (N - 32767) 10,41,41 |
40 IF (N - 32767) 10,41,41 |
||
41 WRITE (6,34) (ALINE(I), I = 1,LL) |
41 WRITE (6,34) (ALINE(I), I = 1,LL) |
||
END</ |
END</syntaxhighlight> |
||
Start of output: |
Start of output: |
||
Line 1,498: | Line 1,496: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
Function isPrime(n As Integer) As Boolean |
Function isPrime(n As Integer) As Boolean |
||
Line 1,520: | Line 1,518: | ||
Print : Print |
Print : Print |
||
Print "Press any key to quit" |
Print "Press any key to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,536: | Line 1,534: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
An unbounded cascading filtering method using channels, adapted from the classic concurrent prime sieve example in the "Try Go" window at http://golang.org/, improved by postponing the initiation of the filtering by a prime until the prime's square is seen in the input. |
An unbounded cascading filtering method using channels, adapted from the classic concurrent prime sieve example in the "Try Go" window at http://golang.org/, improved by postponing the initiation of the filtering by a prime until the prime's square is seen in the input. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,590: | Line 1,588: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,596: | Line 1,594: | ||
</pre> |
</pre> |
||
A simple iterative method, also unbounded and starting with 2. |
A simple iterative method, also unbounded and starting with 2. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,627: | Line 1,625: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,635: | Line 1,633: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
The most basic: |
The most basic: |
||
< |
<syntaxhighlight lang="haskell">[n | n <- [2..], []==[i | i <- [2..n-1], rem n i == 0]]</syntaxhighlight> |
||
With trial division emulated by additions (the seeds of Sieve): |
With trial division emulated by additions (the seeds of Sieve): |
||
< |
<syntaxhighlight lang="haskell">[n | n <- [2..], []==[i | i <- [2..n-1], j <- [i,i+i..n], j==n]]</syntaxhighlight> |
||
With recursive filtering (in wrong order, from bigger to smaller natural numbers): |
With recursive filtering (in wrong order, from bigger to smaller natural numbers): |
||
< |
<syntaxhighlight lang="haskell">foldr (\x r -> x : filter ((> 0).(`rem` x)) r) [] [2..]</syntaxhighlight> |
||
With iterated sieving (in right order, from smaller to bigger primes): |
With iterated sieving (in right order, from smaller to bigger primes): |
||
< |
<syntaxhighlight lang="haskell">Data.List.unfoldr (\(x:xs) -> Just (x, filter ((> 0).(`rem` x)) xs)) [2..]</syntaxhighlight> |
||
A proper [[Primality by trial division#Haskell|primality testing by trial division]] can be used to produce short ranges of primes more efficiently: |
A proper [[Primality by trial division#Haskell|primality testing by trial division]] can be used to produce short ranges of primes more efficiently: |
||
< |
<syntaxhighlight lang="haskell">primesFromTo n m = filter isPrime [n..m]</syntaxhighlight> |
||
The standard optimal trial division version has <code>isPrime</code> in the above inlined: |
The standard optimal trial division version has <code>isPrime</code> in the above inlined: |
||
< |
<syntaxhighlight lang="haskell">-- primes = filter isPrime [2..] |
||
primes = 2 : [n | n <- [3..], foldr (\p r-> p*p > n || rem n p > 0 && r) |
primes = 2 : [n | n <- [3..], foldr (\p r-> p*p > n || rem n p > 0 && r) |
||
True primes]</ |
True primes]</syntaxhighlight> |
||
It is easy to amend this to test only odd numbers by only odd primes, or automatically skip the multiples of ''3'' (also, ''5'', etc.) by construction as well (a ''wheel factorization'' technique): |
It is easy to amend this to test only odd numbers by only odd primes, or automatically skip the multiples of ''3'' (also, ''5'', etc.) by construction as well (a ''wheel factorization'' technique): |
||
< |
<syntaxhighlight lang="haskell">primes = 2 : 3 : [n | n <- [5,7..], foldr (\p r-> p*p > n || rem n p > 0 && r) |
||
True (drop 1 primes)] |
True (drop 1 primes)] |
||
= [2,3,5] ++ [n | n <- scanl (+) 7 (cycle [4,2]), |
= [2,3,5] ++ [n | n <- scanl (+) 7 (cycle [4,2]), |
||
foldr (\p r-> p*p > n || rem n p > 0 && r) |
foldr (\p r-> p*p > n || rem n p > 0 && r) |
||
True (drop 2 primes)] |
True (drop 2 primes)] |
||
-- = [2,3,5,7] ++ [n | n <- scanl (+) 11 (cycle [2,4,2,4,6,2,6,4]), ... (drop 3 primes)]</ |
-- = [2,3,5,7] ++ [n | n <- scanl (+) 11 (cycle [2,4,2,4,6,2,6,4]), ... (drop 3 primes)]</syntaxhighlight> |
||
It is also easy to extend the above in generating the factorization wheel automatically as follows: |
It is also easy to extend the above in generating the factorization wheel automatically as follows: |
||
< |
<syntaxhighlight lang="haskell">-- autogenerates wheel primes, first sieve prime, and gaps |
||
wheelGen :: Int -> ([Int],Int,[Int]) |
wheelGen :: Int -> ([Int],Int,[Int]) |
||
wheelGen n = loop 1 3 [2] [2] where |
wheelGen n = loop 1 3 [2] [2] where |
||
Line 1,691: | Line 1,689: | ||
| any ((==) 0 . rem n) |
| any ((==) 0 . rem n) |
||
(takeWhile ((<= n) . flip (^) 2) bps) = xtrprms (n + g) gs' |
(takeWhile ((<= n) . flip (^) 2) bps) = xtrprms (n + g) gs' |
||
| otherwise = n : xtrprms (n + g) gs'</ |
| otherwise = n : xtrprms (n + g) gs'</syntaxhighlight> |
||
This is likely about the fastest of the trial division prime generators at just a few seconds to generate the primes up to ten million, which is about the limit of its practical range. An incremental Sieve of Eratosthenes sieve will extend the useful range about ten times this and isn't that much more complex. |
This is likely about the fastest of the trial division prime generators at just a few seconds to generate the primes up to ten million, which is about the limit of its practical range. An incremental Sieve of Eratosthenes sieve will extend the useful range about ten times this and isn't that much more complex. |
||
Line 1,697: | Line 1,695: | ||
===Sieve by trial division=== |
===Sieve by trial division=== |
||
The classic David Turner's 1983 (1976? 1975?) SASL code repeatedly ''sieves'' a stream of candidate numbers from those divisible by a prime at a time, and works even for unbounded streams, thanks to lazy evaluation: |
The classic David Turner's 1983 (1976? 1975?) SASL code repeatedly ''sieves'' a stream of candidate numbers from those divisible by a prime at a time, and works even for unbounded streams, thanks to lazy evaluation: |
||
< |
<syntaxhighlight lang="haskell">primesT = sieve [2..] |
||
where |
where |
||
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0] |
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0] |
||
-- map head |
-- map head |
||
-- . iterate (\(p:xs) -> filter ((> 0).(`rem` p)) xs) $ [2..]</ |
-- . iterate (\(p:xs) -> filter ((> 0).(`rem` p)) xs) $ [2..]</syntaxhighlight> |
||
As shown in Melissa O'Neill's paper [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], its complexity is quadratic in number of primes produced whereas that of optimal trial division is <math>O(n^{1.5}/(\log n)^{0.5})</math>, and of true SoE it is <math>O(n\log n\log\log n)</math>, in ''n'' primes produced. |
As shown in Melissa O'Neill's paper [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], its complexity is quadratic in number of primes produced whereas that of optimal trial division is <math>O(n^{1.5}/(\log n)^{0.5})</math>, and of true SoE it is <math>O(n\log n\log\log n)</math>, in ''n'' primes produced. |
||
Line 1,709: | Line 1,707: | ||
===Bounded sieve by trial division=== |
===Bounded sieve by trial division=== |
||
Bounded formulation has normal trial division complexity, because it can stop early via an explicit guard: |
Bounded formulation has normal trial division complexity, because it can stop early via an explicit guard: |
||
< |
<syntaxhighlight lang="haskell">primesTo m = sieve [2..m] |
||
where |
where |
||
sieve (p:xs) | p*p > m = p : xs |
sieve (p:xs) | p*p > m = p : xs |
||
| otherwise = p : sieve [x | x <- xs, rem x p /= 0] |
| otherwise = p : sieve [x | x <- xs, rem x p /= 0] |
||
-- (\(a,b:_) -> map head a ++ b) . span ((< m).(^2).head) |
-- (\(a,b:_) -> map head a ++ b) . span ((< m).(^2).head) |
||
-- $ iterate (\(p:xs) -> filter ((>0).(`rem`p)) xs) [2..m]</ |
-- $ iterate (\(p:xs) -> filter ((>0).(`rem`p)) xs) [2..m]</syntaxhighlight> |
||
===Postponed sieve by trial division=== |
===Postponed sieve by trial division=== |
||
{{trans|Racket}} |
{{trans|Racket}} |
||
To make it unbounded, the guard cannot be simply discarded. The firing up of a filter by a prime should be ''postponed'' until its ''square'' is seen amongst the candidates (so a bigger chunk of input numbers are taken straight away as primes, between each opening up of a new filter, instead of just one head element in the non-postponed algorithm): |
To make it unbounded, the guard cannot be simply discarded. The firing up of a filter by a prime should be ''postponed'' until its ''square'' is seen amongst the candidates (so a bigger chunk of input numbers are taken straight away as primes, between each opening up of a new filter, instead of just one head element in the non-postponed algorithm): |
||
< |
<syntaxhighlight lang="haskell">primesPT = sieve primesPT [2..] |
||
where |
where |
||
sieve ~(p:ps) (x:xs) = x : after (p*p) xs |
sieve ~(p:ps) (x:xs) = x : after (p*p) xs |
||
Line 1,726: | Line 1,724: | ||
| otherwise = f (x:xs) |
| otherwise = f (x:xs) |
||
-- fix $ concatMap (fst.fst) . iterate (\((_,t),p:ps) -> |
-- fix $ concatMap (fst.fst) . iterate (\((_,t),p:ps) -> |
||
-- (span (< head ps^2) [x | x <- t, rem x p > 0], ps)) . (,) ([2,3],[4..])</ |
-- (span (< head ps^2) [x | x <- t, rem x p > 0], ps)) . (,) ([2,3],[4..])</syntaxhighlight> |
||
<code>~(p:ps)</code> is a lazy pattern: the matching will be delayed until any of its variables are actually needed. Here it means that on the very first iteration the head of <code>primesPT</code> will be safely accessed only after it is already defined (by <code>x : after (p*p) ...</code>). |
<code>~(p:ps)</code> is a lazy pattern: the matching will be delayed until any of its variables are actually needed. Here it means that on the very first iteration the head of <code>primesPT</code> will be safely accessed only after it is already defined (by <code>x : after (p*p) ...</code>). |
||
Line 1,732: | Line 1,730: | ||
Note that the above introduced laziness for the evaluation of the head of the base primes list in order to avoid a race isn't necessary for the usual method of just introducing the first of the base primes before starting the computation as follows (use the same `wheelGen` as above for this wheel factorized version): |
Note that the above introduced laziness for the evaluation of the head of the base primes list in order to avoid a race isn't necessary for the usual method of just introducing the first of the base primes before starting the computation as follows (use the same `wheelGen` as above for this wheel factorized version): |
||
< |
<syntaxhighlight lang="haskell">primesPTDW :: () -> [Int] -- nested filters, no matter how much postponed, |
||
primesPTDW() = -- causes mucho allocation of deferred thunks! |
primesPTDW() = -- causes mucho allocation of deferred thunks! |
||
wheelPrimes ++ _Y ((firstSievePrime :) . sieve cndts) where |
wheelPrimes ++ _Y ((firstSievePrime :) . sieve cndts) where |
||
Line 1,740: | Line 1,738: | ||
q = bp * bp |
q = bp * bp |
||
after (x:xs') | x >= q = sieve (filter ((> 0) . (`rem` bp)) xs') bps' |
after (x:xs') | x >= q = sieve (filter ((> 0) . (`rem` bp)) xs') bps' |
||
| otherwise = x : after xs'</ |
| otherwise = x : after xs'</syntaxhighlight> |
||
However, these postponed solutions are slower than the last of the basic trial division prime generators as the (nested) filters add greatly the the deferred "thunks" stored to the heap rather than the more direct (and more strict) determination of whether a number is prime as it's output. |
However, these postponed solutions are slower than the last of the basic trial division prime generators as the (nested) filters add greatly the the deferred "thunks" stored to the heap rather than the more direct (and more strict) determination of whether a number is prime as it's output. |
||
Line 1,746: | Line 1,744: | ||
===Segmented Generate and Test=== |
===Segmented Generate and Test=== |
||
Explicating the run-time list of ''filters'' (created implicitly by the sieves above) as a list of ''factors to test by'' on each segment between the consecutive squares of primes (so that no testing is done prematurely), and rearranging to avoid recalculations, leads to the following: |
Explicating the run-time list of ''filters'' (created implicitly by the sieves above) as a list of ''factors to test by'' on each segment between the consecutive squares of primes (so that no testing is done prematurely), and rearranging to avoid recalculations, leads to the following: |
||
< |
<syntaxhighlight lang="haskell">import Data.List (inits) |
||
primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST) |
primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST) |
||
where |
where |
||
sieve x q ps (fs:ft) = filter (\y-> all ((/=0).rem y) fs) [x,x+2..q-2] |
sieve x q ps (fs:ft) = filter (\y-> all ((/=0).rem y) fs) [x,x+2..q-2] |
||
++ sieve (q+2) (head ps^2) (tail ps) ft</ |
++ sieve (q+2) (head ps^2) (tail ps) ft</syntaxhighlight> |
||
<code>inits</code> makes a stream of (progressively growing) prefixes of an input stream, starting with an empty prefix, here making the <code>fs</code> parameter to get a sequence of values <code>[], [3], [3,5], ...</code>. |
<code>inits</code> makes a stream of (progressively growing) prefixes of an input stream, starting with an empty prefix, here making the <code>fs</code> parameter to get a sequence of values <code>[], [3], [3,5], ...</code>. |
||
Line 1,762: | Line 1,760: | ||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang="j">primTrial=:3 :0 |
||
try=. i.&.(p:inv) %: >./ y |
try=. i.&.(p:inv) %: >./ y |
||
candidate=. (y>1)*y=<.y |
candidate=. (y>1)*y=<.y |
||
y #~ candidate*(y e.try) = +/ 0= try|/ y |
y #~ candidate*(y e.try) = +/ 0= try|/ y |
||
)</ |
)</syntaxhighlight> |
||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang="j"> primTrial 1e6+i.100 |
||
1000003 1000033 1000037 1000039 1000081 1000099</ |
1000003 1000033 1000037 1000039 1000081 1000099</syntaxhighlight> |
||
Note that this is a filter - it selects values from its argument which are prime. If no suitable values are found the resulting sequence of primes will be empty. |
Note that this is a filter - it selects values from its argument which are prime. If no suitable values are found the resulting sequence of primes will be empty. |
||
Line 1,781: | Line 1,779: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|8}} |
{{works with|Java|8}} |
||
< |
<syntaxhighlight lang="java">import java.util.stream.IntStream; |
||
public class Test { |
public class Test { |
||
Line 1,805: | Line 1,803: | ||
getPrimes(0, 100).forEach(p -> System.out.printf("%d, ", p)); |
getPrimes(0, 100).forEach(p -> System.out.printf("%d, ", p)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,</pre> |
<pre>2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,</pre> |
||
Line 1,813: | Line 1,811: | ||
This entry uses is_prime/0 as defined at [[Primality_by_trial_division#jq]]. |
This entry uses is_prime/0 as defined at [[Primality_by_trial_division#jq]]. |
||
< |
<syntaxhighlight lang="jq"># Produce a (possibly empty) stream of primes in the range [m,n], i.e. m <= p <= n |
||
def primes(m; n): |
def primes(m; n): |
||
([m,2] | max) as $m |
([m,2] | max) as $m |
||
Line 1,819: | Line 1,817: | ||
elif $m == 2 then 2, primes(3;n) |
elif $m == 2 then 2, primes(3;n) |
||
else (1 + (2 * range($m/2 | floor; (n + 1) /2 | floor))) | select( is_prime ) |
else (1 + (2 * range($m/2 | floor; (n + 1) /2 | floor))) | select( is_prime ) |
||
end;</ |
end;</syntaxhighlight> |
||
'''Examples:''' |
'''Examples:''' |
||
<lang |
<syntaxhighlight lang="jq">primes(0;10)</syntaxhighlight> |
||
< |
<syntaxhighlight lang="sh">2 |
||
3 |
3 |
||
5 |
5 |
||
7</ |
7</syntaxhighlight> |
||
Produce an array of primes, p, satisfying 50 <= p <= 99: |
Produce an array of primes, p, satisfying 50 <= p <= 99: |
||
<lang |
<syntaxhighlight lang="jq">[primes(50;99)]</syntaxhighlight> |
||
[53,59,61,67,71,73,79,83,89,97] |
[53,59,61,67,71,73,79,83,89,97] |
||
Line 1,836: | Line 1,834: | ||
I've chosen to solve this task by creating a new iterator type, <tt>TDPrimes</tt>. <tt>TDPrimes</tt> contains the upper limit of the sequence. The iteration state is the list of computed primes, and the item returned with each iteration is the current prime. The core of the solution is the <tt>next</tt> method for <tt>TDPrimes</tt>, which computes the next prime by trial division of the previously determined primes contained in the iteration state. |
I've chosen to solve this task by creating a new iterator type, <tt>TDPrimes</tt>. <tt>TDPrimes</tt> contains the upper limit of the sequence. The iteration state is the list of computed primes, and the item returned with each iteration is the current prime. The core of the solution is the <tt>next</tt> method for <tt>TDPrimes</tt>, which computes the next prime by trial division of the previously determined primes contained in the iteration state. |
||
< |
<syntaxhighlight lang="julia">struct TDPrimes{T<:Integer} |
||
uplim::T |
uplim::T |
||
end |
end |
||
Line 1,853: | Line 1,851: | ||
end |
end |
||
println("Primes ≤ 100: ", join((p for p in TDPrimes(100)), ", "))</ |
println("Primes ≤ 100: ", join((p for p in TDPrimes(100)), ", "))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,859: | Line 1,857: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.0.6 |
||
fun isPrime(n: Int): Boolean { |
fun isPrime(n: Int): Boolean { |
||
Line 1,885: | Line 1,883: | ||
if (count % 15 == 0) println() |
if (count % 15 == 0) println() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,914: | Line 1,912: | ||
=={{header|Lambdatalk}}== |
=={{header|Lambdatalk}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
{def prime |
{def prime |
||
{def prime.rec |
{def prime.rec |
||
Line 1,931: | Line 1,929: | ||
{map prime {serie 9901 10000 2}} |
{map prime {serie 9901 10000 2}} |
||
-> 9901 9907 9923 9929 9931 9941 9949 9967 9973 |
-> 9901 9907 9923 9929 9931 9941 9949 9967 9973 |
||
</syntaxhighlight> |
|||
</lang> |
|||
More to see in [http://epsilonwiki.free.fr/lambdaway/?view=primes2] |
More to see in [http://epsilonwiki.free.fr/lambdaway/?view=primes2] |
||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
<syntaxhighlight lang="lb"> |
|||
<lang lb> |
|||
print "Rosetta Code - Sequence of primes by trial division" |
print "Rosetta Code - Sequence of primes by trial division" |
||
print: print "Prime numbers between 1 and 50" |
print: print "Prime numbers between 1 and 50" |
||
Line 1,956: | Line 1,954: | ||
isPrime=1 |
isPrime=1 |
||
end function |
end function |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,986: | Line 1,984: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">-- Returns true if x is prime, and false otherwise |
||
function isprime (x) |
function isprime (x) |
||
if x < 2 then return false end |
if x < 2 then return false end |
||
Line 2,018: | Line 2,016: | ||
-- Main procedure |
-- Main procedure |
||
show(primes(100)) |
show(primes(100)) |
||
show(primes(50, 150))</ |
show(primes(50, 150))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
||
Line 2,024: | Line 2,022: | ||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[primeq] |
||
primeq[1]:=False |
primeq[1]:=False |
||
primeq[2]:=True |
primeq[2]:=True |
||
Line 2,030: | Line 2,028: | ||
AllTrue[Range[2,Sqrt[n]+1],Mod[n,#]!=0&] |
AllTrue[Range[2,Sqrt[n]+1],Mod[n,#]!=0&] |
||
] |
] |
||
Select[Range[100],primeq]</ |
Select[Range[100],primeq]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}</pre> |
<pre>{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}</pre> |
||
=={{header|MATLAB}}== |
=={{header|MATLAB}}== |
||
< |
<syntaxhighlight lang="matlab">function primeList = sieveOfEratosthenes(lastNumber) |
||
list = (2:lastNumber); %Construct list of numbers |
list = (2:lastNumber); %Construct list of numbers |
||
Line 2,049: | Line 2,047: | ||
primeList = [primeList list]; %The rest of the numbers in the list are primes |
primeList = [primeList list]; %The rest of the numbers in the list are primes |
||
end</ |
end</syntaxhighlight>{{out|Sample Output}} |
||
sieveOfEratosthenes(30) |
sieveOfEratosthenes(30) |
||
Line 2,058: | Line 2,056: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="nim">import strformat |
||
func isPrime(n: int): bool = |
func isPrime(n: int): bool = |
||
Line 2,080: | Line 2,078: | ||
if count mod 15 == 0: |
if count mod 15 == 0: |
||
write(stdout, "\n") |
write(stdout, "\n") |
||
echo()</ |
echo()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,111: | Line 2,109: | ||
isPrime function is from Primality by trial division page |
isPrime function is from Primality by trial division page |
||
< |
<syntaxhighlight lang="oforth">: primeSeq(n) n seq filter(#isPrime) ;</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">trial(n)={ |
||
if(n < 4, return(n > 1)); /* Handle negatives */ |
if(n < 4, return(n > 1)); /* Handle negatives */ |
||
forprime(p=2,sqrt(n), |
forprime(p=2,sqrt(n), |
||
Line 2,122: | Line 2,120: | ||
}; |
}; |
||
select(trial, [1..100])</ |
select(trial, [1..100])</syntaxhighlight> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
{{libheader|primTrial}} {{works with|Free Pascal}} |
{{libheader|primTrial}} {{works with|Free Pascal}} |
||
Hiding the work in a existing unit. |
Hiding the work in a existing unit. |
||
<syntaxhighlight lang="pascal"> |
|||
<lang Pascal> |
|||
program PrimeRng; |
program PrimeRng; |
||
uses |
uses |
||
Line 2,139: | Line 2,137: | ||
write(Range[i]:12); |
write(Range[i]:12); |
||
writeln; |
writeln; |
||
end.</ |
end.</syntaxhighlight> |
||
;output: |
;output: |
||
<pre> 1000000007 1000000009 1000000021 1000000033 1000000087 1000000093 1000000097</pre> |
<pre> 1000000007 1000000009 1000000021 1000000033 1000000087 1000000093 1000000097</pre> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use v5.36; |
||
use enum <false true>; |
use enum <false true>; |
||
Line 2,157: | Line 2,155: | ||
say join ' ', grep { isprime $_ } 0 .. 100; |
say join ' ', grep { isprime $_ } 0 .. 100; |
||
say join ' ', grep { isprime $_ } 12345678 .. 12345678+100;</ |
say join ' ', grep { isprime $_ } 12345678 .. 12345678+100;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
||
Line 2,164: | Line 2,162: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Exact copy of [[Primality_by_trial_division#Phix]] |
Exact copy of [[Primality_by_trial_division#Phix]] |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">is_prime_by_trial_division</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;">is_prime_by_trial_division</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;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
Line 2,177: | Line 2,175: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">32</span><span style="color: #0000FF;">),</span><span style="color: #000000;">is_prime_by_trial_division</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">32</span><span style="color: #0000FF;">),</span><span style="color: #000000;">is_prime_by_trial_division</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,184: | Line 2,182: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de prime? (N) |
||
(or |
(or |
||
(= N 2) |
(= N 2) |
||
Line 2,198: | Line 2,196: | ||
(filter prime? (range A B)) ) |
(filter prime? (range A B)) ) |
||
(println (primeseq 50 99))</ |
(println (primeseq 50 99))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(53 59 61 67 71 73 79 83 89 97)</pre> |
<pre>(53 59 61 67 71 73 79 83 89 97)</pre> |
||
Line 2,206: | Line 2,204: | ||
This is based on the wheel sieve Mark 1 in the paper, where candidates are taken from increasing size factorization wheels, where the next wheel of increasing size is used after the current wheel is completely "rolled." |
This is based on the wheel sieve Mark 1 in the paper, where candidates are taken from increasing size factorization wheels, where the next wheel of increasing size is used after the current wheel is completely "rolled." |
||
<syntaxhighlight lang="picolisp"> |
|||
<lang PicoLisp> |
|||
(de comma_fmt (N) (format N 0 "." ",")) |
(de comma_fmt (N) (format N 0 "." ",")) |
||
Line 2,247: | Line 2,245: | ||
(prinl "The 10,001st prime is " (comma_fmt (primes T))) |
(prinl "The 10,001st prime is " (comma_fmt (primes T))) |
||
(bye) |
(bye) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 2,255: | Line 2,253: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function eratosthenes ($n) { |
function eratosthenes ($n) { |
||
if($n -ge 1){ |
if($n -ge 1){ |
||
Line 2,278: | Line 2,276: | ||
} |
} |
||
"$(sieve-start-end 100 200)" |
"$(sieve-start-end 100 200)" |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 2,286: | Line 2,284: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Creates a 2,3,5 factorization wheel to eliminate the majority of divisors and prime candidates before filtering. |
Creates a 2,3,5 factorization wheel to eliminate the majority of divisors and prime candidates before filtering. |
||
<syntaxhighlight lang="prolog"> |
|||
<lang Prolog> |
|||
wheel235(L) :- |
wheel235(L) :- |
||
W = [6, 4, 2, 4, 2, 4, 6, 2 | W], |
W = [6, 4, 2, 4, 2, 4, 6, 2 | W], |
||
Line 2,308: | Line 2,306: | ||
roll235wheel(Limit, Candidates), |
roll235wheel(Limit, Candidates), |
||
include(prime235, Candidates, Primes). |
include(prime235, Candidates, Primes). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 2,322: | Line 2,320: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">EnableExplicit |
||
#SPC=Chr(32) |
#SPC=Chr(32) |
||
#TB=~"\t" |
#TB=~"\t" |
||
Line 2,370: | Line 2,368: | ||
Print(~"\nPrimes= "+Str(*count\i)) |
Print(~"\nPrimes= "+Str(*count\i)) |
||
Input() |
Input() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Input (n1<n2 & n1>0) |
<pre>Input (n1<n2 & n1>0) |
||
Line 2,392: | Line 2,390: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Using the basic ''prime()'' function from: [http://rosettacode.org/wiki/Primality_by_trial_division#Python "Primality by trial division"] |
Using the basic ''prime()'' function from: [http://rosettacode.org/wiki/Primality_by_trial_division#Python "Primality by trial division"] |
||
<syntaxhighlight lang="python"> |
|||
<lang Python> |
|||
def prime(a): |
def prime(a): |
||
return not (a < 2 or any(a % x == 0 for x in xrange(2, int(a**0.5) + 1))) |
return not (a < 2 or any(a % x == 0 for x in xrange(2, int(a**0.5) + 1))) |
||
Line 2,398: | Line 2,396: | ||
def primes_below(n): |
def primes_below(n): |
||
return [i for i in range(n) if prime(i)] |
return [i for i in range(n) if prime(i)] |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>>>> primes_below(100) |
<pre>>>> primes_below(100) |
||
Line 2,404: | Line 2,402: | ||
===Fun With Lists=== |
===Fun With Lists=== |
||
< |
<syntaxhighlight lang="python">limiter = 100 |
||
primelist = [] |
primelist = [] |
||
def primer(n): |
def primer(n): |
||
Line 2,420: | Line 2,418: | ||
print(len(primelist)) |
print(len(primelist)) |
||
print(primelist)</ |
print(primelist)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,432: | Line 2,430: | ||
Make a nest of primes less than n. |
Make a nest of primes less than n. |
||
< |
<syntaxhighlight lang="quackery">[ [] swap times |
||
[ i^ isprime if |
[ i^ isprime if |
||
[ i^ join ] ] ] is primes< ( n --> [ ) |
[ i^ join ] ] ] is primes< ( n --> [ ) |
||
100 primes< echo</ |
100 primes< echo</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 2,450: | Line 2,448: | ||
This example uses infinite lists (streams) to implement a sieve algorithm that produces all prime numbers. |
This example uses infinite lists (streams) to implement a sieve algorithm that produces all prime numbers. |
||
< |
<syntaxhighlight lang="racket">#lang lazy |
||
(define nats (cons 1 (map add1 nats))) |
(define nats (cons 1 (map add1 nats))) |
||
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l)) |
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l)) |
||
(define (sieve l) (cons (first l) (sieve (sift (first l) (rest l))))) |
(define (sieve l) (cons (first l) (sieve (sift (first l) (rest l))))) |
||
(define primes (sieve (rest nats))) |
(define primes (sieve (rest nats))) |
||
(!! (take 25 primes))</ |
(!! (take 25 primes))</syntaxhighlight> |
||
==== Optimized with postponed processing ==== |
==== Optimized with postponed processing ==== |
||
Line 2,461: | Line 2,459: | ||
Since a prime's multiples that count start from its square, we should only add them when we reach that square. |
Since a prime's multiples that count start from its square, we should only add them when we reach that square. |
||
< |
<syntaxhighlight lang="racket">#lang lazy |
||
(define nats (cons 1 (map add1 nats))) |
(define nats (cons 1 (map add1 nats))) |
||
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l)) |
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l)) |
||
Line 2,470: | Line 2,468: | ||
(λ(t) (sieve (sift (car ps) t) (cdr ps)))))) |
(λ(t) (sieve (sift (car ps) t) (cdr ps)))))) |
||
(define primes (sieve (cdr nats) primes)) |
(define primes (sieve (cdr nats) primes)) |
||
(!! (take 25 primes))</ |
(!! (take 25 primes))</syntaxhighlight> |
||
=== Using threads and channels === |
=== Using threads and channels === |
||
Line 2,476: | Line 2,474: | ||
Same algorithm as above, but now using threads and channels to produce a channel of all prime numbers (similar to newsqueak). The macro at the top is a convenient wrapper around definitions of channels using a thread that feeds them. |
Same algorithm as above, but now using threads and channels to produce a channel of all prime numbers (similar to newsqueak). The macro at the top is a convenient wrapper around definitions of channels using a thread that feeds them. |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define-syntax (define-thread-loop stx) |
(define-syntax (define-thread-loop stx) |
||
(syntax-case stx () |
(syntax-case stx () |
||
Line 2,493: | Line 2,491: | ||
(let ([x (channel-get c)]) (out! x) (set! c (sift x c)))) |
(let ([x (channel-get c)]) (out! x) (set! c (sift x c)))) |
||
(define primes (let ([ns (nats)]) (channel-get ns) (sieve ns))) |
(define primes (let ([ns (nats)]) (channel-get ns) (sieve ns))) |
||
(for/list ([i 25] [x (in-producer (λ() (channel-get primes)))]) x)</ |
(for/list ([i 25] [x (in-producer (λ() (channel-get primes)))]) x)</syntaxhighlight> |
||
=== Using generators === |
=== Using generators === |
||
Line 2,499: | Line 2,497: | ||
Yet another variation of the same algorithm as above, this time using generators. |
Yet another variation of the same algorithm as above, this time using generators. |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(require racket/generator) |
(require racket/generator) |
||
(define nats (generator () (for ([i (in-naturals 1)]) (yield i)))) |
(define nats (generator () (for ([i (in-naturals 1)]) (yield i)))) |
||
Line 2,508: | Line 2,506: | ||
(generator () (let loop ([g g]) (let ([x (g)]) (yield x) (loop (sift x g)))))) |
(generator () (let loop ([g g]) (let ([x (g)]) (yield x) (loop (sift x g)))))) |
||
(define primes (begin (nats) (sieve nats))) |
(define primes (begin (nats) (sieve nats))) |
||
(for/list ([i 25] [x (in-producer primes)]) x)</ |
(for/list ([i 25] [x (in-producer primes)]) x)</syntaxhighlight> |
||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
Here is a straightforward implementation of the naive algorithm. |
Here is a straightforward implementation of the naive algorithm. |
||
<lang |
<syntaxhighlight lang="raku" line>constant @primes = 2, 3, { first * %% none(@_), (@_[* - 1], * + 2 ... *) } ... *; |
||
say @primes[^100];</ |
say @primes[^100];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2 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 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541</pre> |
<pre>2 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 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541</pre> |
||
Line 2,525: | Line 2,523: | ||
Usage note: by using a negative number (for the program's argument), the list of primes is suppressed, but the prime count is still shown. |
Usage note: by using a negative number (for the program's argument), the list of primes is suppressed, but the prime count is still shown. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program lists a sequence of primes by testing primality by trial division. */ |
||
parse arg n . /*get optional number of primes to find*/ |
parse arg n . /*get optional number of primes to find*/ |
||
if n=='' | n=="," then n= 26 /*Not specified? Then use the default.*/ |
if n=='' | n=="," then n= 26 /*Not specified? Then use the default.*/ |
||
Line 2,542: | Line 2,540: | ||
end /*j*/ /* [↑] only display N number of primes*/ |
end /*j*/ /* [↑] only display N number of primes*/ |
||
/* [↓] display number of primes found.*/ |
/* [↓] display number of primes found.*/ |
||
say # ' primes found.' /*stick a fork in it, we're all done. */</ |
say # ' primes found.' /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default input: <tt> 26 </tt>}} |
{{out|output|text= when using the default input: <tt> 26 </tt>}} |
||
<pre> |
<pre> |
||
Line 2,577: | Line 2,575: | ||
This version shows how the REXX program may be optimized further by extending the list of low primes and |
This version shows how the REXX program may be optimized further by extending the list of low primes and |
||
<br>the special low prime divisions (the <big>'''//'''</big> tests, which is the ''remainder'' when doing division). |
<br>the special low prime divisions (the <big>'''//'''</big> tests, which is the ''remainder'' when doing division). |
||
< |
<syntaxhighlight lang="rexx">/*REXX program lists a sequence of primes by testing primality by trial division. */ |
||
parse arg N . /*get optional number of primes to find*/ |
parse arg N . /*get optional number of primes to find*/ |
||
if N=='' | N=="," then N= 26 /*Not specified? Then assume default.*/ |
if N=='' | N=="," then N= 26 /*Not specified? Then assume default.*/ |
||
Line 2,603: | Line 2,601: | ||
end /*j*/ /* [↑] only display N number of primes*/ |
end /*j*/ /* [↑] only display N number of primes*/ |
||
/* [↓] display number of primes found.*/ |
/* [↓] display number of primes found.*/ |
||
say # ' primes found.' /*stick a fork in it, we're all done. */</ |
say # ' primes found.' /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br> |
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
for i = 1 to 100 |
for i = 1 to 100 |
||
if isPrime(i) see "" + i + " " ok |
if isPrime(i) see "" + i + " " ok |
||
Line 2,621: | Line 2,619: | ||
next |
next |
||
return true |
return true |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
The Prime class in the standard library has several Prime generators. In some methods it can be specified which generator will be used. The generator can be used on it's own: |
The Prime class in the standard library has several Prime generators. In some methods it can be specified which generator will be used. The generator can be used on it's own: |
||
< |
<syntaxhighlight lang="ruby">require "prime" |
||
pg = Prime::TrialDivisionGenerator.new |
pg = Prime::TrialDivisionGenerator.new |
||
p pg.take(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] |
p pg.take(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] |
||
p pg.next # => 31</ |
p pg.next # => 31</syntaxhighlight> |
||
===By Trial Division w/Prime Generator=== |
===By Trial Division w/Prime Generator=== |
||
See https://rosettacode.org/wiki/Primality_by_trial_division#Ruby |
See https://rosettacode.org/wiki/Primality_by_trial_division#Ruby |
||
< |
<syntaxhighlight lang="ruby">def primep5?(n) # P5 Prime Generator primality test |
||
# P5 = 30*k + {7,11,13,17,19,23,29,31} # P5 primes candidates sequence |
# P5 = 30*k + {7,11,13,17,19,23,29,31} # P5 primes candidates sequence |
||
return [2, 3, 5].include?(n) if n < 7 # for small and negative values |
return [2, 3, 5].include?(n) if n < 7 # for small and negative values |
||
Line 2,648: | Line 2,646: | ||
# Create sequence of primes from 1_000_000_001 to 1_000_000_201 |
# Create sequence of primes from 1_000_000_001 to 1_000_000_201 |
||
n = 1_000_000_001; n.step(n+200, 2) { |p| puts p if primep5?(p) }</ |
n = 1_000_000_001; n.step(n+200, 2) { |p| puts p if primep5?(p) }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1000000007 |
<pre>1000000007 |
||
Line 2,662: | Line 2,660: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust"> |
||
fn is_prime(number: u32) -> bool { |
fn is_prime(number: u32) -> bool { |
||
#[allow(clippy::cast_precision_loss)] |
#[allow(clippy::cast_precision_loss)] |
||
Line 2,682: | Line 2,680: | ||
); |
); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,690: | Line 2,688: | ||
=={{header|S-BASIC}}== |
=={{header|S-BASIC}}== |
||
< |
<syntaxhighlight lang="basic"> |
||
comment |
comment |
||
Prime number generator in S-BASIC. Only odd numbers are |
Prime number generator in S-BASIC. Only odd numbers are |
||
Line 2,745: | Line 2,743: | ||
print "All done. Goodbye" |
print "All done. Goodbye" |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,756: | Line 2,754: | ||
===Odds-Only "infinite" primes generator using Streams and Co-Inductive Streams=== |
===Odds-Only "infinite" primes generator using Streams and Co-Inductive Streams=== |
||
Using Streams, [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf the "unfaithful sieve"], i.e. '''sub-optimal trial division sieve'''. |
Using Streams, [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf the "unfaithful sieve"], i.e. '''sub-optimal trial division sieve'''. |
||
< |
<syntaxhighlight lang="scala">def sieve(nums: Stream[Int]): Stream[Int] = |
||
Stream.cons(nums.head, sieve((nums.tail).filter(_ % nums.head != 0))) |
Stream.cons(nums.head, sieve((nums.tail).filter(_ % nums.head != 0))) |
||
val primes = 2 #:: sieve(Stream.from(3, 2)) |
val primes = 2 #:: sieve(Stream.from(3, 2)) |
||
println(primes take 10 toList) // //List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29) |
println(primes take 10 toList) // //List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29) |
||
println(primes takeWhile (_ < 30) toList) //List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</ |
println(primes takeWhile (_ < 30) toList) //List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</syntaxhighlight> |
||
{{out}}Both println statements give the same results: |
{{out}}Both println statements give the same results: |
||
<pre>List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</pre> |
<pre>List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</pre> |
||
Line 2,769: | Line 2,767: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
Using the ''is_prime()'' function from: [http://rosettacode.org/wiki/Primality_by_trial_division#Sidef "Primality by trial division"] |
Using the ''is_prime()'' function from: [http://rosettacode.org/wiki/Primality_by_trial_division#Sidef "Primality by trial division"] |
||
< |
<syntaxhighlight lang="ruby">func prime_seq(amount, callback) { |
||
var (counter, number) = (0, 0); |
var (counter, number) = (0, 0); |
||
while (counter < amount) { |
while (counter < amount) { |
||
Line 2,780: | Line 2,778: | ||
} |
} |
||
prime_seq(100, {|p| say p}); # prints the first 100 primes</ |
prime_seq(100, {|p| say p}); # prints the first 100 primes</syntaxhighlight> |
||
=={{header|Spin}}== |
=={{header|Spin}}== |
||
Line 2,788: | Line 2,786: | ||
{{works with|HomeSpun}} |
{{works with|HomeSpun}} |
||
{{works with|OpenSpin}} |
{{works with|OpenSpin}} |
||
< |
<syntaxhighlight lang="spin">con |
||
_clkmode = xtal1+pll16x |
_clkmode = xtal1+pll16x |
||
_clkfreq = 80_000_000 |
_clkfreq = 80_000_000 |
||
Line 2,810: | Line 2,808: | ||
waitcnt(_clkfreq + cnt) |
waitcnt(_clkfreq + cnt) |
||
ser.stop</ |
ser.stop</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 2,817: | Line 2,815: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">import Foundation |
||
extension SequenceType { |
extension SequenceType { |
||
Line 2,839: | Line 2,837: | ||
} |
} |
||
return pastPrimes.last |
return pastPrimes.last |
||
}</ |
}</syntaxhighlight> |
||
===Simple version=== |
===Simple version=== |
||
{{works with|Swift 2 and Swift 3}} |
{{works with|Swift 2 and Swift 3}} |
||
< |
<syntaxhighlight lang="swift">var primes = [2] |
||
func trialPrimes(_ max:Int){ |
func trialPrimes(_ max:Int){ |
||
Line 2,862: | Line 2,860: | ||
trialPrimes(100) |
trialPrimes(100) |
||
print(primes)</ |
print(primes)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,870: | Line 2,868: | ||
=={{header|Tailspin}}== |
=={{header|Tailspin}}== |
||
Simplest version |
Simplest version |
||
< |
<syntaxhighlight lang="tailspin"> |
||
templates ifPrime |
templates ifPrime |
||
def n: $; |
def n: $; |
||
Line 2,882: | Line 2,880: | ||
100 -> primes -> '$; |
100 -> primes -> '$; |
||
' -> !OUT::write |
' -> !OUT::write |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,890: | Line 2,888: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
As we're generating a sequence of primes, we can use that sequence of primes to describe what we're filtering against. |
As we're generating a sequence of primes, we can use that sequence of primes to describe what we're filtering against. |
||
< |
<syntaxhighlight lang="tcl">set primes {} |
||
proc havePrime n { |
proc havePrime n { |
||
global primes |
global primes |
||
Line 2,905: | Line 2,903: | ||
} |
} |
||
} |
} |
||
puts ""</ |
puts ""</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,914: | Line 2,912: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
Using a simple generator. |
Using a simple generator. |
||
< |
<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt |
||
var primeSeq = Fiber.new { |
var primeSeq = Fiber.new { |
||
Line 2,942: | Line 2,940: | ||
if (count%15 == 0) System.print() |
if (count%15 == 0) System.print() |
||
if (count == limit) break |
if (count == limit) break |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,970: | Line 2,968: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is prime |
||
int N, I; |
int N, I; |
||
[if N <= 2 then return N = 2; |
[if N <= 2 then return N = 2; |
||
Line 2,984: | Line 2,982: | ||
for N:= 2 to 100 do |
for N:= 2 to 100 do |
||
if IsPrime(N) then |
if IsPrime(N) then |
||
[IntOut(0, N); ChOut(0, ^ )]</ |
[IntOut(0, N); ChOut(0, ^ )]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,992: | Line 2,990: | ||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
< |
<syntaxhighlight lang="yabasic">sub isPrime(v) |
||
if v < 2 then return False : fi |
if v < 2 then return False : fi |
||
if mod(v, 2) = 0 then return v = 2 : fi |
if mod(v, 2) = 0 then return v = 2 : fi |
||
Line 3,006: | Line 3,004: | ||
if isPrime(i) print str$(i), " "; |
if isPrime(i) print str$(i), " "; |
||
next i |
next i |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Igual que la entrada de FreeBASIC.</pre> |
<pre>Igual que la entrada de FreeBASIC.</pre> |
||
Line 3,013: | Line 3,011: | ||
The code in [[Extensible prime generator#zkl]] is a much better solution to this problem. |
The code in [[Extensible prime generator#zkl]] is a much better solution to this problem. |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="zkl">fcn isPrime(p){ |
||
(p>=2) and (not [2 .. p.toFloat().sqrt()].filter1('wrap(n){ p%n==0 })) |
(p>=2) and (not [2 .. p.toFloat().sqrt()].filter1('wrap(n){ p%n==0 })) |
||
} |
} |
||
fcn primesBelow(n){ [0..n].filter(isPrime) }</ |
fcn primesBelow(n){ [0..n].filter(isPrime) }</syntaxhighlight> |
||
The Method filter1 stops at the first non False result, which, if there is one, is the first found diviser, thus short cutting the rest of the test. |
The Method filter1 stops at the first non False result, which, if there is one, is the first found diviser, thus short cutting the rest of the test. |
||
< |
<syntaxhighlight lang="zkl">primesBelow(100).toString(*).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |