Sieve of Atkin For Finding all Primes Up-to N.
Hello Friends, Welcome to my other blog on competitive
programming. Today, I am going to continue one advance mathematical concept that already we started
in previous blog .As you might have already figured out that today’s we
are going to discuss Sieve of primes using the Atkin’s approach. So,
without wasting much time, let’s get started.
The Sieve of Atkin is a modern algorithm for finding all
prime numbers up to a specified integer. Compared with the ancient sieve of
Eratosthenes, which marks off multiple of squares of primes, thus
achieving a better theoretical asymptotic complexity.
The Sieve of Atkin is an efficient algorithm used
to find all prime number upto a given number(say N) and does so in O(N)
time complexity. With a modified version with enumerating lattice points
variation, the time complexity goes to O(N / log log N). Sieve of Atkin
is computationally efficient than Sieve of Eratosthenes as it marks multiple of
square of prime numbers.
Algorithm:
- Create a list named result list and fill it with:
- 2, 3 and 5
- Create a list named sieve list with an entry for each positive integer and intially mark them as non prime
- For each entry number N in the sieve list, find the modulo-sixty remainder r (remainder when N is divided by 60) for N:
- If r is 1, 13, 17, 29, 37, 41, 49, or 53:
- flip the entry for each possible solution to 4x^2 + y^2 = N.
- All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-twelve remainder of 1 or 5. These numbers are prime if and only if the number of solutions to 4×^2+y^2=n is odd and the number is square free. A square free integer is one which is not divisible by any perfect square other than 1.
- If r is 7, 19, 31, or 43:
- lip the entry for each possible solution to 3x^2 + y^2 = N.
- All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x^2 + y^2 = n is odd and the number is square free.
- If r is 11, 23, 47, or 59:
- flip the entry for each possible solution to 3x^2 – y^2 = N when x > y.
- All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x^2 – y^2 = n is odd and the number is square free.
- If r is something else, ignore it completely.
- Start with the lowest number in the sieve list
- Take the next number in the sieve list still marked prime
- Include the number in the final list
- Square the number and mark all multiples of that square as non-prime. Note that the multiples that can be factored by 2, 3, or 5 need not be marked, as these will be ignored in the final enumeration of primes
Time complexity: Θ(N)
Space complexity: Θ(N)
The algorithm described above can compute primes up to N using O(N) operations with only O(N) bits of memory.Sieve of Eratosthenes which uses O(N log log N) operations and the same O(N^1/2/log N) bits of memory plus a minimal page buffer.
Sieve of Atkin (modified enumerating lattice points variation)
Time complexity: Θ(N / (log log N))
Space complexity: Θ(N^0.5)
A special modified
"enumerating lattice points" variation which is not the above version
of the Sieve of Atkin can theoretically compute primes up to N using O( N / log
log N) operations with N^1/2 + o(1) bits of memory but this variation is rarely
implemented.
That is a little better
in performance at a very high cost in memory as compared to both the ordinary
page segmented version and to an equivalent but rarely-implemented version
of the sieve of Eratosthenes which uses O(N) operations and O(N^1/2(log log N)/log N) bits of memory.
Explanation:
The algorithm
completely ignores any numbers with remainder modulo 60 that is divisible by
two, three, or five, since numbers with a modulo 60 remainder divisible by one
of these three primes are themselves divisible by that prime.
All numbers n with modulo-sixty remainder 1, 13, 17,
29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are
prime if and only if the number of solutions to 4x2 + y2 = n is odd and the number is squarefree
.
All numbers n with modulo-sixty remainder 7, 19, 31,
or 43 have a modulo-six remainder of 1. These numbers are prime if and only if
the number of solutions to 3x2 + y2 = n is odd and the number is squarefree .
All numbers n with modulo-sixty remainder 11, 23, 47,
or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only
if the number of solutions to 3x2 − y2 = n is odd and the number is squarefree .
None of the potential primes are divisible
by 2, 3, or 5, so they can't be divisible by their squares. This is why
squarefree checks don't include 22, 32, and 52.
#include <stdio.h>
#include<stdlib.h>
int
main()
{
int
result,fresult;
int i,
j, a, b, c;
unsigned char *satkin;
printf("Enter a number up to which all primes are
calculated:\n ");
scanf("%d",
&result);
/*allocates
the memory and also initializes the allocates memory block to zero*/
satkin= (unsigned
char *) calloc(result, sizeof(unsigned char));
fresult=
sqrt(result);
for
(a=1;a<=fresult;a++) {
for
(b=1;b<=fresult;b++) {
c=4*a*a+b*b;
if
(c<=result&& (c % 60 ==1||c%60==13||c%60==17||c%60==29||c%60==37||c
%60==41||c%60==49|| c % 60 == 53)) {
satkin[c] =
!satkin[c];
}
c =3*a*a+b*b;
if (c<=
result&& (c % 60 ==7 ||c % 60 ==19|| c % 60==31 || c% 60==43)) {
satkin[c] = !satkin[c];}
c=3* a* a -b*b;
if (a>b && c <= result&& (c % 60 == 11||c %60==23||c % 60== 47||c %60==59))
{
satkin[c] = !satkin[c];
}
}
}
for (i =5;i <= fresult; i++) {
if (satkin[i]==1) {
for (j=1;j * i * i <= result; j++) {
satkin[j * i * i] = 0;
}
}
}
printf("The following primes have been calculated:\n");
for (i = 5; i <=
result; i++) {
if (satkin[i]==1) {
printf("\n%d",
i);
}
}scanf("%d", &i);
return 0;
}
Did you find some great strategies of your own in
this blog?!
If you did, then what are the exciting ones you found
in terms of competitive coding —and how are you planning on implementing them?
Let us know in the comments
Comments
Post a Comment