Hirdetés

Keresés

Új hozzászólás Aktív témák

  • EQMontoya

    veterán

    válasz Pttypang #5222 üzenetére

    Ejj, ha!

    No, akkor okítsunk. :)

    Először is: osztóJa! :)
    Másodszor: szájbaszexuálnád a nevemben, aki arra nevel, hogy magyar változóneveket és függvényneveket használjatok? :)
    Harmadszor: Optimalizáljunk:
    -Ha a megadott szám kisebb, mint 1000, akkor elég a megadott számig menni. Tehát a ciklusfeltétel: i<min(n,1000). Illetve ennek is elég a feléig menni, mert különben ugyanazokat a számokat találod meg fordítva. Tehát i<=min(n,1000)/2. Azért kisebbegyenlő, mert kihasználtam gonoszul az egész osztást.
    -Gondolkodjunk is: a második ciklus tök felesleges. Minden számhoz csak egy másik olyan tartozik, amivel összeadva az öszeg n lesz. Tehát, amit vizsgálnod kell: prime(i) && prime(n-i). Ezzel kész is vagy.

    Tehát:

    for(i=1;i<=min(n,1000)/2;i++)
    {
    if(prime(i) && prime(n-i))
    {
    printf(...);
    }
    }

    No, ez már így nem is lenne rossz, most már cak a prímtesztelést kell kicsit okosítani. Maradjunk a primitív módszereknél, de ennél azért kicsit okosabban. Ha egy szám nem prím, akkor előáll két szám szorzataként. Ebből a kettőből az egyik kisebb, vagy egyenlő, mint a gyöke, tehát elég addig nézni.
    Osztókat számolni tök felesleges, az első osztónál ugyanis biztosan nem lehet prím.

    Tehát:

    for(i=2;i<=sqrt(n);i++)
    {
    if(!n%i) //csalok: ez akkor igaz, ha a maradékos osztás maradéka 0 - tehát osztható
    {
    return false; //van osztója, ami nem egy és nem önmaga
    }
    }
    return true; //ha a gyökéig nem volt osztója, biztos prím.

    Máris mennyivel szebb, ugye? :)

  • Jester01

    veterán

    válasz Pttypang #5222 üzenetére

    1. gyök(n)-ig mész, vagy szitálsz
    2. csak azokat írod ki, ahol a második prím nagyobb vagy egyenlő mint az első (vagyis a második ciklus i-től induljon)

Új hozzászólás Aktív témák