AKS test for primes: Difference between revisions
m (→{{header|Python}}: Tidy.) |
|||
Line 21: | Line 21: | ||
;Reference: |
;Reference: |
||
* [http://www.youtube.com/watch?v=HvMSRWTE2mI Fool-Proof Test for Primes] - Numberphile (Video). |
* [http://www.youtube.com/watch?v=HvMSRWTE2mI Fool-Proof Test for Primes] - Numberphile (Video). |
||
=={{header|C}}== |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
|||
long long c[100]; |
|||
void coef(int n) |
|||
{ |
|||
int i, j; |
|||
if (n < 0 || n > 63) abort(); // gracefully deal with range issue |
|||
for (c[i=0] = 1; i < n; c[0] = -c[0], i++) |
|||
for (c[1 + (j=i)] = 1; j > 0; j--) |
|||
c[j] = c[j-1] - c[j]; |
|||
} |
|||
int is_prime(int n) |
|||
{ |
|||
int i; |
|||
coef(n); |
|||
c[0] += 1, c[i=n] -= 1; |
|||
while (i-- && !(c[i] % n)); |
|||
return i < 0; |
|||
} |
|||
void show(int n) |
|||
{ |
|||
do printf("%+lldx^%d", c[n], n); while (n--); |
|||
} |
|||
int main(void) |
|||
{ |
|||
int n; |
|||
for (n = 0; n < 10; n++) { |
|||
coef(n); |
|||
printf("(x-1)^%d = ", n); |
|||
show(n); |
|||
putchar('\n'); |
|||
} |
|||
printf("\nprimes (never mind the 1):"); |
|||
for (n = 1; n <= 63; n++) |
|||
if (is_prime(n)) |
|||
printf(" %d", n); |
|||
putchar('\n'); |
|||
return 0; |
|||
}</lang> |
|||
The ugly output: |
|||
<pre> |
|||
(x-1)^0 = +1x^0 |
|||
(x-1)^1 = +1x^1-1x^0 |
|||
(x-1)^2 = +1x^2-2x^1+1x^0 |
|||
(x-1)^3 = +1x^3-3x^2+3x^1-1x^0 |
|||
(x-1)^4 = +1x^4-4x^3+6x^2-4x^1+1x^0 |
|||
(x-1)^5 = +1x^5-5x^4+10x^3-10x^2+5x^1-1x^0 |
|||
(x-1)^6 = +1x^6-6x^5+15x^4-20x^3+15x^2-6x^1+1x^0 |
|||
(x-1)^7 = +1x^7-7x^6+21x^5-35x^4+35x^3-21x^2+7x^1-1x^0 |
|||
(x-1)^8 = +1x^8-8x^7+28x^6-56x^5+70x^4-56x^3+28x^2-8x^1+1x^0 |
|||
(x-1)^9 = +1x^9-9x^8+36x^7-84x^6+126x^5-126x^4+84x^3-36x^2+9x^1-1x^0 |
|||
primes (never mind the 1): 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 23:18, 6 February 2014
The AKS test for primes states that a number is prime if all the coefficients of the polynomial expansion of
are divisible by .
For example, trying :
- And all the coefficients are divisible by 3 so 3 is prime by the AKS test.
- The task
- Create a function/subroutine/method that given p generates the coefficients of the expanded polynomial representation of .
- Use the function to show here the polynomial expansions of p for p in the range 0 to at least 7, inclusive.
- Use the previous function in creating another function that when given p returns whether p is prime using the AKS test.
- Use your AKS test to generate a list of all primes under 35.
- As a stretch goal, generate all primes under 50 (Needs greater than 31 bit integers).
- Reference
- Fool-Proof Test for Primes - Numberphile (Video).
C
<lang c>#include <stdio.h>
- include <stdlib.h>
long long c[100];
void coef(int n) { int i, j;
if (n < 0 || n > 63) abort(); // gracefully deal with range issue
for (c[i=0] = 1; i < n; c[0] = -c[0], i++) for (c[1 + (j=i)] = 1; j > 0; j--) c[j] = c[j-1] - c[j]; }
int is_prime(int n) { int i;
coef(n); c[0] += 1, c[i=n] -= 1; while (i-- && !(c[i] % n));
return i < 0; }
void show(int n) { do printf("%+lldx^%d", c[n], n); while (n--); }
int main(void) { int n;
for (n = 0; n < 10; n++) { coef(n); printf("(x-1)^%d = ", n); show(n); putchar('\n'); }
printf("\nprimes (never mind the 1):"); for (n = 1; n <= 63; n++) if (is_prime(n)) printf(" %d", n);
putchar('\n'); return 0; }</lang>
The ugly output:
(x-1)^0 = +1x^0 (x-1)^1 = +1x^1-1x^0 (x-1)^2 = +1x^2-2x^1+1x^0 (x-1)^3 = +1x^3-3x^2+3x^1-1x^0 (x-1)^4 = +1x^4-4x^3+6x^2-4x^1+1x^0 (x-1)^5 = +1x^5-5x^4+10x^3-10x^2+5x^1-1x^0 (x-1)^6 = +1x^6-6x^5+15x^4-20x^3+15x^2-6x^1+1x^0 (x-1)^7 = +1x^7-7x^6+21x^5-35x^4+35x^3-21x^2+7x^1-1x^0 (x-1)^8 = +1x^8-8x^7+28x^6-56x^5+70x^4-56x^3+28x^2-8x^1+1x^0 (x-1)^9 = +1x^9-9x^8+36x^7-84x^6+126x^5-126x^4+84x^3-36x^2+9x^1-1x^0 primes (never mind the 1): 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61
Python
<lang python>def expand_x_1(p):
if p == 0: return [1] ex = [1, -1] for i in range(1, p): ex = [x - y for x,y in zip(ex+[0], [0]+ex)] return ex[::-1]
def aks_test(p):
if p < 2: return False ex = expand_x_1(p) ex[0] += 1 return not any(mult % p for mult in ex[0:-1])
print('# p: (x-1)^p for small p') for p in range(12):
print('%3i: %s' % (p, ' '.join('%+i%s' % (e, ('X^%i' % n) if n else ) for n,e in enumerate(expand_x_1(p)))))
print('\n# small primes using the aks test') print([p for p in range(101) if aks_test(p)])</lang>
- Output:
# p: (x-1)^p for small p 0: +1 1: -1 +1X^1 2: +1 -2X^1 +1X^2 3: -1 +3X^1 -3X^2 +1X^3 4: +1 -4X^1 +6X^2 -4X^3 +1X^4 5: -1 +5X^1 -10X^2 +10X^3 -5X^4 +1X^5 6: +1 -6X^1 +15X^2 -20X^3 +15X^4 -6X^5 +1X^6 7: -1 +7X^1 -21X^2 +35X^3 -35X^4 +21X^5 -7X^6 +1X^7 8: +1 -8X^1 +28X^2 -56X^3 +70X^4 -56X^5 +28X^6 -8X^7 +1X^8 9: -1 +9X^1 -36X^2 +84X^3 -126X^4 +126X^5 -84X^6 +36X^7 -9X^8 +1X^9 10: +1 -10X^1 +45X^2 -120X^3 +210X^4 -252X^5 +210X^6 -120X^7 +45X^8 -10X^9 +1X^10 11: -1 +11X^1 -55X^2 +165X^3 -330X^4 +462X^5 -462X^6 +330X^7 -165X^8 +55X^9 -11X^10 +1X^11 # small primes using the aks test [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]