Thu Nov 21 16:33:19 2024

Algorithmic Cryptanalysis (View it on amazon.com)

A CRC Press Book by Antoine Joux

Program 4.1: Basic code for Eratostenes's sieve

Algorithmic cryptanalysis codes by Antoine Joux are licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License.

#include <stdio.h>
#include <stdlib.h>


typedef unsigned int packedbool;
packedbool *_IsPrime;

#define NpckBool (8*sizeof(packedbool))
#define GetIsPrime(x) \
   (_IsPrime[(x-1)/NpckBool]>>((x-1)%NpckBool))&1
#define SetCompo(x) \
   _IsPrime[(x-1)/NpckBool]&=~(1UL<<((x-1)%NpckBool))


SievePrimes(int Limit)
{
  int i,j, tabLimit;

  tabLimit=(Limit+NpckBool-1)/NpckBool;
  for (i=0;i<tabLimit;i++) _IsPrime[i]=~0;

  for (i=2;i*i<=Limit;i++){

    if (GetIsPrime(i)) {
      for (j=i*i;j<=Limit;j+=i){

        SetCompo(j); } } }

  printf("List of primes up to %d:\n",Limit);
  for (i=2;i<=Limit;i++){

    if (GetIsPrime(i)) {
      printf("%d\n",i); } } }

main()
{
  int Limit;
  printf("Enter limit ?");
  scanf("%d",&Limit);

  _IsPrime=(packedbool *)malloc((Limit+NpckBool-1)/8);

  SievePrimes(Limit);
  free(_IsPrime);
}

Credits for page styles: Dynamic Drive CSS Library