Hogy néz ki egy prímszám kiíró program c++ ban?

if( prime(i)==true && prime(i+14)==true)

{

tomb[i]=i;

counter++;

}

Ez így nem feltétlenül fog működni :) A prime(int) függvényem egy amolyan elfajzott prímtesztelő, mivel csak akkor működik, ha az adott számig minden egyes prímet végigvizsgálsz vele.

Amúgy sztem működne, csak épenséggel lassú lenne, mivel ki kellene számolni az összes értéket. És tök feleslegesen nézne meg egy jó pár elemet.

A helyes megoldás egy primtesztelő algoritmus lenne:

pl a fermat féle teszt( bár ebben lesz egy pár amiben nem csak primek maradnak bent, a jobb megoldás a Miller-Rabin féle primteszt lenne.

legszebb egy primek tipus alkotása lenne, ami eldöntenél, hogy mi prim és mi nem prim. És sokkal hatékonyabb lenne, mint a brute force algoritmus, és akár nagy( 2048 bites) számok körében is működne( persze ehhez biginteger osztályra is szükség van egyelőre itt van longgal;. Ugyanis egyáltalán nem biztos, hogy p meg p+14 is prim lesz kicsi számok esetében.

pl. így( az egyes részfüggvényeket nem implementálom, mert szerintem egy kicsit hosszú lenne, a konstruktort jelenleg kihagytam)

class primek

{

int lnko(int a,b);

int jacobi_symbol(int a, int b, n);

long number;

bool fermat(int numberone);

bool miller(int numbertwo);

bool savoljai(int numberthree);

public:

int getnumber(int szam)

{

number=(long) szam);

return 0;

}

bool prime()

{

if( fermat(number)==true && miller(number)==true && savoljai(number)==true)

{

return true;

else

{

return false;

}

}

};

Ezután az osztályt meghívnánk

Ezt lehet tudni?

Keressük meg adott számig a legtöbb osztójú természetes számot!