Keresés prímszám
Algoritmusok → Search prímszámok
Mivel szeretem megoldani a különböző matematikai problémák (projecteuler.net. Diofant.ru.), Folyamatosan kell csinálni ugyanazt a műveletet. Ezért hoztam létre a blog „algoritmusok”, amely rendszeresen olvasó funkciók különböző feladatokat. Azt hiszem, sok hasznos lesz.
Az érdeklődők is osztoznak. Linkek más oldalakra nem kell dobni, aki azt akarja, hogy ő fogja találni a keresőkben. Rajongója vagyok a C ++, így minden a szintaxis legyen ellene.
Prímszám - egy szám, amely osztható csak egy és önmagában.
Az első funkció ellenőrzi, hogy a szám prím. Ehhez hívja meg a függvényt, átadva azt a számot, amit ellenőrizni kell az egyszerűségre.
A második funkció a következő prímszám szám után, amit át függvényargumentum.
Fontos! Mindkét funkció, akkor ellenőrizze a többiek elosztjuk a kívánt számú két (mivel a készüléket úgy, hogy lesz osztva maradék nélkül), hogy a gyökér a számunkat. Fontos, hogy optimalizáljuk a kódot, amely lehetővé teszi számunkra, hogy a munka nagy számban. Enélkül a keresési értékek jelentősen lelassul.
és ha átírjuk az algoritmus gépi kód? ) Érdekes lenne mérni, hogy mennyi teljesítmény növekedést.
és ha átírjuk az algoritmus gépi kód? ) És cross-platform hordozhatóságát törött kódot.
Nos, ez nem a Java. Csak azt mondtam, hogy írni a kódot egy adott processzor elérése érdekében a lehető legjobb teljesítményt. Az algoritmus egyszerű, és lehet a különböző rendszer parancsok másolni, nem veszít semmit.
Az előadás során írok holnap cikket :)
Köszönöm, hogy hasznos munkát.
Elv továbbra is fenntartják a listát prímszámok és oszthatóság ellenőrzést rajtuk. Mivel ha a szám nem osztható olyan prímszám, ez is a legegyszerűbb.
Ez különösen felgyorsítja az algoritmus nagy számban, mert kihagyja az összes nagy tömbök a számok
Tudom, az ingatlan :)
Nos, eddig nem tudom, hogyan kell végrehajtani rövid és édes. A jövőben, remélem, én korrigálni
Nos, például, hogy van egy lista, amelyben írd le az összes prímszám található. A hurok feltétel helyébe:
Syntax már nem igaz a C # hasonló, de a lényege az ilyen transzferek. Lista egy listából, már csak azt kell beszúrni hozzáadásával más prímszám. Ez ízlés, vagy térjen vissza, vagy már olyan funkciók használatával
Kísérlet, lássuk, hogyan igazolja magát :)
Az én tapasztalatom szerint, van 2 majdnem azonos sebességgel módszert kell találni az első néhány millió prímszám:
1. Szita A Eratosthenes,
2. ellenőrzi a feloszthatóságát páratlan számok az eredmények már prímszámok (az érték előtt négyzetgyöke számát teszt).
Megértem a lényege ezeknek a módszereknek ugyanazt, de a megközelítés különböző irányból. És így kiderül, hogy a szitán Eratosthenes kell fogyasztani sokkal több memóriát, mert Ez megköveteli pre-tömb összes szám kisebb, mint a maximális kívánt.
Ie mert ez azt megtalálod prímszám akár egymillió, szükségünk van egy sor 999 999 szám 2-1 millió és abban az esetben a oszthatóság számok tömb áll csak prímszámok
Vagy van valamilyen megvalósítása a szita nem emészti meg a memória?
A szita lehet használni bittérképes. Work lassabb lesz, de nem tudom, hogy sokkal lassabb.
1. A szita hangsúlyt nagyszámú egyszerű műveletek (kiegészítés)
2. A második módszer szerint, egy kis mennyiségű stressz lassú műveletek (osztás maradékos).
bizonyos értelemben kell tekinteni indikátorként 1 bites prímszám, és 0 jelentése nincs jelen, akkor a bitek számát a tömb számának meghatározásához a?
Őszintén szólva, a bitmap nem működik, és milyen nehéz megvalósítani az nincs jelen, de az ötlet az átviteli e rács formájában egy kép (bitmap) elég érdekes))
Felvevő egység i-edik bit a tömbben a. álló 32-bites számok:
Reading nem nehéz. By the way, ez lehet egy alkalommal ellenőrzi a szám 32 a könnyű összehasonlítani a megfelelő cella tömb egy 0xffffffff.
Nem lenne sokkal érdekesebb lefordítani az algoritmus egy bináris algebra. Akkor lehetséges, hogy optimalizálja az összes műveletet. A modern processzorok fejlett matematikai parancsokat, hogy fel lehetne használni, hogy megkerülje az univerzális fordító. Ha tettem valamit, mint ez sokáig az x86-os utasításkészletet. De ahhoz, hogy végre egy ilyen rendszer intel64 csapatok lenne sokkal érdekesebb.