Primality by trial division: Difference between revisions
Content added Content deleted
({{out}}) |
|||
Line 1: | Line 1: | ||
{{task|Prime Numbers}}Write a boolean function that tells whether a given integer is prime. Remember that 1 and all non-positive numbers are not prime. |
{{task|Prime Numbers}}Write a boolean function that tells whether a given integer is prime. Remember that 1 and all non-positive numbers are not prime. |
||
Use trial division. Even numbers over two may be eliminated right away. |
Use trial division. Even numbers over two may be eliminated right away. |
||
A loop from <span style="font-family:serif">3</span> to <span style="font-family:serif">√n</span> will suffice, but other loops are allowed. |
|||
* Related tasks: [[Sequence of primes by Trial Division]], [[Sieve of Eratosthenes]], [[Prime decomposition]], [[AKS test for primes]]. |
* Related tasks: [[Sequence of primes by Trial Division]], [[Sieve of Eratosthenes]], [[Prime decomposition]], [[AKS test for primes]]. |
||
Line 303: | Line 304: | ||
NEXT |
NEXT |
||
= TRUE</lang> |
= TRUE</lang> |
||
{{out}} |
|||
'''Output:''' |
|||
<pre> |
<pre> |
||
2 is prime |
2 is prime |
||
Line 817: | Line 818: | ||
PAUSE |
PAUSE |
||
</lang> |
</lang> |
||
{{out}} |
|||
Output |
|||
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 |
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 |
||
Press any key to continue...</pre> |
Press any key to continue...</pre> |
||
Line 1,877: | Line 1,878: | ||
/*Note: // is modulus. */ |
/*Note: // is modulus. */ |
||
return 1 /*done dividing, it's prime.*/</lang> |
return 1 /*done dividing, it's prime.*/</lang> |
||
{{out}} when using the default input of 10000 |
|||
<pre style="height:20ex"> |
<pre style="height:20ex"> |
||
2 is prime. |
2 is prime. |
||
Line 2,376: | Line 2,377: | ||
until Num = 0</lang> |
until Num = 0</lang> |
||
{{out}} |
|||
Example output: |
|||
<pre> |
<pre> |
||
777777777 |
777777777 |