Álprímek

A Kis-Fermat-tétel szerint p|a^p-a, minden p prímre és a egészre. Az viszont nem igaz, hogy ha az oszthatóság teljesül, akkor p prím. (Épp ezért a Kis-Fermat-tétellell csak ,,valószínűségi'' alapon tudjuk eldönteni egy számról, hogy prím-e.) Azokat a számokat, melyekre teljesül az oszthatóság minden a-ra, de összetettek, álprímeknek nevezzük. Ezen az oldalon az álprímkereséssel foglalkozunk.

Az első néhány álprím: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633, 1024651, 1033669, 1050985, 1082809. Mint látható, az álprímek igen ritkák. Ahhoz, hogy egy ilyen listát elkészítsünk, az alábbihoz hasonló programot kell futtatni napestig:

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

#if 0
  #define num unsigned int
  #define nump "%d"
#endif
#if 0
  #define num unsigned long
  #define nump "%ld"
#endif
#if 1
  #define num unsigned long long
  #define nump "%Ld"
#endif

num hatvanyoz(num x, num n, num m) { /* by Knuth */
  num y, z;
  int b;
  y=1;
  if (m<2 || !x) {
    y=0;
  } else if (x!=1) {
    z=x%m;
    while (1) {
      b=n&1;
      n>>=1;
      if (b) {
        y*=z; if (y>=m) y%=m;
        if (!n) break;
      }
      z*=z; if (z>=m) z%=m;
    }
  }
  return y;
}

int prim_e(num l) {
  num d=5, s=5;
  if (l<=7) return (l!=4 && l!=6);
  if (!(l&1) || !(l%3)) return 0;
  while (s<=l) {
    if (!(l%d)) return 0;
    s+=4+(d<<2);
    d+=2;
    if (s>l) break;
    if (!(l%d)) return 0;
    s+=16+(d<<3);
    d+=4;
  }
  return 1;
}

num lnko(num a, num b) { /* 0,0-ra rossz */
  num r;
  while (1) {
    if (!a) return b;
    if (!b) return a;
    if (a==1 || b==1) return 1;
    r=b%a;
    b=a;
    a=r;
  }
}

int pprim_e(num l) {
  num i, m;
  if (!(l&1)) return 0;
  for (i=2;i<l;i++) {
    if (lnko(i,l)!=1) continue;
    m=hatvanyoz(i,l-1,l);
    if (m!=1) return 0;
  }
  return 1;
}

char milyen(num l) {
  if (!pprim_e(l)) return '.';
  if (prim_e(l)) return 'p';
  return 's';
}

/*	prim	pprim
.		0	osszetett
s	0	1	alprim
p	1	1	prim */

int main(int argc, char **argv) {
  num i, debug=0;
  char c;
  if (argc<2) i=0;
  else if (argc==2) i=atol(argv[1]);
  else if (argc==3) { i=atol(argv[1]); debug=1; }
  if (debug) {
    while (1) {
      if ((c=milyen(i))=='s') printf(nump "\n", i);
      putc(c, stderr);
      i++;
      if (!(i&8191)) { fflush(stdout); fflush(stderr); }
    }
  } else {
    while (1) {
      if ((c=milyen(i))=='s') printf(nump "\n", i);
      i++;
      if (!(i&8191)) fflush(stdout);
    }
  }
  return 0;
}

A programnak első paraméterként megadható, hogy honnan induljon a keresés. Ha második paramétert is kap, akkor a stderr-re számonként egy-egy byte-ot ('.', 's' vagy 'p') ír.

Ez a lap pts oldalai közül való.