Olyan prímszámok, melyek szorzatából 1-et kivonva újra prímszámot kapunk?

Ha a legprimitívebb módon kezdünk bele akkor írj egy függvényt ami megállapítja egy számról, hogy prim-e ?

Ha megvan szólj.

Szia!

Eljárás

int[] primtomb = eltárolt prímek (neten van ezerféle algoritmus rá)

int []szorzatPrimTomb = megfelelő prímek (végeredmény)

int tombmutato = 0

ciklus int aktSzorzando=0 aktSzorzando<primtomb hossza aktSzorzando++

ciklus int aktSzorzo=0 aktSzorzo< primtomb hossza aktSzorzo++

ciklus int aktSzorzat =0 aktSzorzat<primtomb hossza aktSzorzat++

Ha primtomb[aktSzorzando]* primtomb[aktSzorzo] -1 = primtomb[aktSzorzat]

Akkor szorzatPrimTomb[tombmutato] = primtomb[aktSzorzat]

tombmutato ++

Ciklus vége

Ciklus vége

Ciklus vége

Eljárás vége

Eléggé időigényes folyamat, mondhatni egyáltalán nem optimalizált, de házinak=kiindulási pontnak megfelelő.

Remélem érthető volt.

Ryo

Ja és a tömbmutató növelése persze a ha elágazás igaz ágán belül van...

Ryo

#include <cstdlib>

#include <iostream>

#include <math.h>

using namespace std;

bool prime(int szam){

bool jo = true ;

if (szam == 2) return true;

if ((szam % 2 == 0) || (szam == 1)) return false;

for (int t = 3; t <= sqrt(szam) + 1; t += 2) if (szam % t == 0) jo = false ;

return jo ;

}

int main(){

int a = 2;

for (int b = 1; b < 1000; b++) if (prime(b)) if (prime((a * b) - 1)) cout << a << " x " << b << " - 1 = " << (a * b) - 1 << endl;

system("PAUSE");

return 0;

}

A matematikai részét majd egy tanult ember elmagyarázza, hogy 'a' miért csak a kettő.

Mivel senki sem döngeti az ajtókat ezért megpróbálom elmesélni. Páratlan szám páratlannal való szorzása szintén páratlant eredményez. Most 'dobjuk' ki a kettőt a prímek közül és látjuk, hogy az összes páratlan :) Ha egy páratlan számból egyet elveszünk akkor az páros, innentől már megint csak a kettő játszik az egyik oldalon. A másik sarokban az összes többi prím.

Van aki nem ért egyet ?

Helyes a meglátásod, a pár egyik tagja a kettő, mert a szorzatnak párosnak kell lennie ahhoz, hogy ha kivonunk belőle egyet prím lehessen. Kivétel ha a szorzat 3 (mert 3-1=2 prím), de nincs két olyan prím aminek a szorzata 3, így ezzel nem kell foglalkozni.

Itt egy megvalósítás Pythonban, 10.000.000-ig pillanatok alatt lefut, 100.000.000-hoz kell pár másodperc de még lassabb gépeken is percen belül van még a "lassú" Pythonban is.

max_number = 1000000

number_list = [False] * max_number

primes = set()

for i in range(2, max_number):

. . if not number_list[i]:

. . . . primes.add(i)

. . . . pair = (i+1)//2

. . . . if pair in primes:

. . . . . . print(2, pair)

. . . . for j in range(2*i, max_number, i):

. . . . . . number_list[j] = True

Semmivel sem bonyolultabb a sokkal gyorsabb eratoszthenészi szita algoritmus prím kereséshez. Jó megírni egyszer kezdőként a mindenki által jól ismert alap algoritmust, de rászokni és/vagy rászoktatni másokat arra elég nagy hiba. Érdemes még megfigyelni a (hash) halmazok használatát, amiknek a komplexitása kereséshez O(1). Későbbiek során jól fog jönni.

[link]