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

• sztanozs veterán

  #6274

  #6272 Hunmugli

  2016-09-08 13:43:03

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  sztanozs

  veterán

  #6272 Hunmugli

  #6272 Hunmugli

  Én már a bonyolultabb megoldást választottam: van egy tömb, az tárolja a prímeket. Aztán egyesével eldönti minden számról, hogy prím-e, vagy sem. De Eratosztelész szitája tényleg jobb, csak több hely kell neki - cserébe gyorsabb. Majd megírom a másikat is, főleg ha az első megoldás nem sikerül

  Mekkora a legnagyobb prím, amit tárolni szeretnél?

• PumpkinSeed addikt

  #6273

  #6272 Hunmugli

  2016-09-08 10:44:20

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  PumpkinSeed

  addikt

  #6272 Hunmugli

  #6272 Hunmugli

  Én már a bonyolultabb megoldást választottam: van egy tömb, az tárolja a prímeket. Aztán egyesével eldönti minden számról, hogy prím-e, vagy sem. De Eratosztelész szitája tényleg jobb, csak több hely kell neki - cserébe gyorsabb. Majd megírom a másikat is, főleg ha az első megoldás nem sikerül

  Ez nem egy túl jó megoldás, ugyanis a prím mennyiségének növekedésével jelentősen nő a műveleti idő is, ugyanis minden szám vizsgálatakor megnézed az összes tárolóban lévő prímet. Ebben az esetben n x m művelet fog végrehajtódni ahol az n a vizsgálandó számok mennyisége és m a tömbben lévő prímek mennyisége. Tegyük fel, hogy 100.000 számot akarsz vizsgálni és 40.000 prím van a tömbben (amit amúgy kézzel kellene felvinned) így 4.000.000.000 művelet kellene ahhoz, hogy 100.000 számot megvizsgálj. Ezek most csak számok, de ez túl sok művelet egy ilyen egyszerű feladathoz.

  Ezzel szemben kikukáztam a szita bonyolultságát ami Prim(N)=P(N), ami azt jelenti, hogy ha van N prímszámod akkor N művelet alatt oldja meg. Ami azt jelenti, hogy 100.000 szám esetén ~100.000 műveletből megkeresi őket szóval 40.000x gyorsabb mint az előző megoldás. Ezt amúgy constans complexity-nek hívják.

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