AKS test for primes: Difference between revisions
Content added Content deleted
(→{{header|Perl 6}}: list comprension no longer allowed at statementlist level) |
(→{{header|Ruby}}: Add implementation.) |
||
Line 671: | Line 671: | ||
Primes: 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 |
Primes: 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 |
||
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 </pre> |
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 </pre> |
||
=={{header|Ruby}}== |
|||
Using the `polynomial` Rubygem, this can be written directly from the definition in the description: |
|||
<lang ruby>require 'polynomial' |
|||
def x_minus_1_to_the(p) |
|||
return Polynomial.new(-1,1)**p |
|||
end |
|||
def prime?(p) |
|||
return false if p < 2 |
|||
(x_minus_1_to_the(p) - Polynomial.from_string("x**#{p}-1")).coefs.select{|n| n%p!=0}.length == 0 |
|||
end |
|||
7.times do |n| |
|||
puts "(x-1)^#{n} = #{x_minus_1_to_the(n).to_s}" |
|||
end |
|||
puts "\nPrimes below 50:", 50.times.select {|n| prime? n}.join(',')</lang> |
|||
Or without the dependency: |
|||
<lang ruby>def x_minus_1_to_the(p) |
|||
return [1] if p==0 |
|||
(p-1).times.inject([1,-1]) do |ex, _| |
|||
(ex + [0]).zip([0] + ex).map { |x,y| x - y } |
|||
end.reverse |
|||
end |
|||
def prime?(p) |
|||
return false if p < 2 |
|||
coeff = x_minus_1_to_the(p) |
|||
([coeff[0]+1] + coeff[1,coeff.length-2]).select{|n| n%p!=0}.length == 0 |
|||
end |
|||
7.times do |n| |
|||
puts "(x-1)^#{n} = " + |
|||
x_minus_1_to_the(n). |
|||
each_with_index. |
|||
map { |c, p| "#{c}x^#{p}".sub( /^(-?)1x/, '\1x' ).sub( /\^1$/, '' ).sub( /x\^0/, '1' ) }. |
|||
join( ' + ' ). |
|||
gsub( /\+ -/, '- ' ) |
|||
end |
|||
puts "\nPrimes below 50:", 50.times.select {|n| prime? n}.join(',')</lang> |
|||
=={{header|Rust}}== |
=={{header|Rust}}== |