Hogyan lehet ellenőrizni, hogy egy szám prím

Prímszám - számok osztható csak önmagukban és 1; Az összes többi szám az úgynevezett összetett szám. Számos módja van annak meghatározására, hogy egy szám prím. Egyes eljárások viszonylag egyszerű, de ezek nem alkalmasak nagy számban. Más módszerek hasznos nagyszámú ténylegesen képviseli valószínűségi algoritmusokat, amelyek néha tévesen jellemezhető, mint számos egyszerű vagy összetett.

lépések szerkesztése

1. módszer a 4:
Bust elválasztó szerkesztése

Bust elválasztó - a legegyszerűbb módja, hogy meghatározzák a könnyű. Abban az esetben, kisszámú ez talán még a leggyorsabb módja. Ez alapján meg kell határozni az prímszám: a szám prím, ha nincs osztója nem saját magát, és az egyik.

Legyen n - számot kell vizsgálni. E módszer szerint meg kell osztani a szám n minden lehetséges egész elválasztó. Mert nagy n, például n = 101, ellenőrzés egyes térelválasztó vesz igénybe sok időt. De vannak olyan módon, hogy csökkentsék a számát elválasztó ellenőrizni kívánt.

Döntse száma n páros. Minden páros szám osztható 2. Ha az n egész szám - a páros, akkor azonnal kijelenti, hogy ez nem egy egyszerű (vagyis egy egész szám). Egy gyors meghatározásához a paritás figyelni, hogy az utolsó számjegyét. Ha az utolsó számjegye 2, 4, 6, 8,0, ez a szám még, és nem könnyű.

• Az egyetlen kivétel ez alól - a 2-es szám tehát osztható csak önmagában, és 1, a 2-es szám - egy prímszám. Így a 2-es szám csak páratlan prímszám.

Osszuk n minden egész szám 2-től n-1. Mivel az osztó kisebb, mint az osztalék, az ellenőrzés minden osztója n-nél kisebb és nagyobb, mint 2 kell mutatni, hogy a n prím. Akkor kezdődhet számmal nagyobb, mint 2, mert a páros számok (amelyek többszörösei 2) nem prímszám. Ez nem a leghatékonyabb módja a tesztelésnek primality, de van egy pár módszerek optimalizálása tesztelés.

• Például, ellenőrizze száma 11. Ebben az esetben, szakadék (egyenletesen) 11 3, 4, 5, 6, 7, 8, 9, 10. Mivel sem az egyik ezek a számok nem osztódnak (egyenletes) 11, a 11-es szám - egyszerű számát.

Ahhoz, hogy időt takarít meg, ellenőrizze a térelválasztó négyzetgyökével kerekített érték (n). Check minden osztója 2 és n-1 időigényes lehet. Például, ha azt szeretnénk, hogy ellenőrizze a száma 103, akkor meg kell, hogy teszteljék a következő térelválasztók: 3, 4, 5, 6, 7, és így tovább, egészen a 102! De ezt el lehet kerülni - csak ellenőrizni az elválasztó 2 és lekerekített négyzetgyök (n).

• Magyarázat ezt az elvet. Tekintsük szorzók 100. 100 = 100 × 1, 2 × 50 4 × 25 5 × 20, 10 × 10, 20 × 5 × 25 4 2 × 50, 100 × 1. Megjegyezzük, hogy miután a pár szorzók 10 × 10 minden pár szorzók ismétlődnek (csak elemek ezekben a párban felcserélődnek). Ezért, ha lehet figyelmen kívül hagyni a osztója n nagyobb, mint négyzetgyöke (n).
• Például, n = 37. csekket nem kell tesztelni az összes osztói 3 és 36. Ehelyett a csekket elválasztó között 2 és kerekített érték négyzetgyökének (37).
  • A négyzetgyök (37) = 6.08. Kerek ez a szám 7.
  • 37 nem osztható 3, 4, 5, 6, 7, így - egyszerű.

Hogy tovább időt, tesztelni csak elsődleges osztója. A definíció szerint olyan összetett szám fejezhető a termék két vagy több prímszám. Ezért az osztály számát n szerves térelválasztó - felesleges műveletet addig ismételjük, felosztása n való elsődleges osztója. Így tovább szűkítheti a tesztsorozat elválasztó.

• Ez azt jelenti, hogy minden, még osztók és minden osztója, amely többszöröse prímszám lehet hagyni.
• Például, ellenőrizze száma 103. A négyzetgyöke 103 kerekítve 11. Egyszerű elválasztó 2 és 11 3, 5, 7, 11. elválasztó 4, 6, 8, 9, 10 lehet hagyni (9 többszöröse 3, és az összes többi elválasztó - páros számok). Így, ha már csökkentette a vizsgált elválasztó négy szám.
  • Elválasztó 3, 5, 7, 11 nem osztjuk (egyenletes) száma 103, így - egyszerű.