Forum PHP.pl > liczby pierwsze

Pomoc - Szukaj - Użytkownicy - Kalendarz

Jabol

26.12.2003, 09:53:04

temat wydzielony od: http://forum.php.pl/viewtopic.php?t=9078
Chodzi o sprawdzanie licz czy są pierwsze.

Cytat

Najprosciej (choc nie najwydajniej) sprawdzic podzielnosc liczby X przez wszystkie liczby calkowite od 2 do sqrt(X) (sqrt - pierwiastek kwadratowy). Jesli się przez ktorakolwiek z nich dzieli to nie jest to liczba pierwsza (wyjatkiem jest liczba 2, ktora jest liczba pierwsza).

Najprościej jest podzielić przez wszystkie liczy pierwsze mniejsze od sqrt(X) i większe od 2.

FiDO

27.12.2003, 00:24:42

Cytat

...

Najprościej jest podzielić przez wszystkie liczy pierwsze mniejsze od sqrt(X) i większe od 2.

Najpierw trzebaby je znalezc ;P Nie zeby to bylo trudne, ale kodu bedzie wiecej.

s_w_ir

27.12.2003, 21:32:53

Dobra dzięki za te odpowiedzi. A czy macie rozwiązanie na punkt 2:

Cytat

2. Jak obliczeniami sprawdzić czy liczba jest całkowita(właśnie to mi jest do perla potrzebne), albo prosił bym o funkcje perla sprawdzającą to?

Bo ja robiłem co mogłem i nic.

DeyV

27.12.2003, 21:45:15

z przykrością muszę stwierdzić, że rozsądne wykonanie tego zadania wymaga znajmowości całkiem zaawansowanej matematyki, i napisania całkiem mądrego programu.
Kiedyś widziałem stroną pokazującą jak powinno się to zrobić, oraz program napisany w paskalu, który sprawdzał czy dana liczba jest pierwsza. Podawałem ten link komuś, a osoba ta postanowiła przepisać ten program na php. Jednak działanie php okazało się zawodne - tj. program w paskalu wykonaywał się kilka tys razy szybciej (może pojawiły się jakieś błdy w kodzie php - nie wiem)
W każdym razie temat jest ciekawy, tak wieć zapraszam do googlania

Cudi

27.12.2003, 22:50:16

Temat jest ciekawy, jedak eksperyment który opisuje DeyV nie powiódł sie. To ja byłem tą osoba która próbowała przetłumaczyć ten kod z paskala na php, niestety z nienajlepszym skutkiem

W każdym bądź razie są na polskich stronach opisy programów które potrafią to sprawdzić, są to jednak bardzo skomplikowane procesy korzystające z tzw. sita erostatenesa, i nie wiem czy język typu php lub Perl poradzi sobie z nimi

Jabol

28.12.2003, 09:50:18

mam program w C, który generuje ustaloną liczbę liczb pierwszych.
pierwsze c

Kod

#include <stdio.h>

#include "pierwsze.h"

int dividable( const int, const int[] );

int main( int argc, char * argv[] )

{

    int nrs[ARRSIZE] = { 2, 3, NULL }, i = 1, curr = 3;

#ifdef DEBUG

    fprintf( stderr, "array address: 0x%xn", nrs );

#endif

    puts( "1: 2n2: 3" );

    while( ( curr += 2 )  && ( ( i +  1 ) < ARRSIZE ) )

    {

        if( ! dividable( curr, nrs ) )

        {

            nrs[++i] = curr;

            nrs[i+1] = NULL;

            printf( "%d: %dn", (i + 1), curr );

#ifdef DEBUG

            if( ! ( ( i - 1 ) % NOTIFY ) )

                fprintf( stderr, "found %dn", i );

#endif

        }

    }

    return 0;

}

int dividable( const int nr, const int nrs[] )

{

    int i = 0;

    do

    {

#ifdef DEBUG

        fprintf( stderr, "checking: %d %% %dn", nr, nrs[i] );

#endif

        if( ! ( nr % nrs[i] ) )

            return 1;

    } while( ( nrs[++i] != NULL ) && ( nrs[i] < ( nr / 2 ) ) );

    return 0;

}

pierwsze.h

Kod

// Delete line below if you don't want to have debugging shit on the screen

#define DEBUG 1

// How many numbers do you wanna get

#define ARRSIZE 10

// Each how many numbers do you wanna be notified ? ( ignored if debug offed )

#define NOTIFY 2

Co prawda tutaj mam łatwiej, bo korzystam z wytworzonej wcześniej tabeli liczb pierwszych. Pamiętam, że jak generowałem pierwszy milion to sżło chyba z pare godzin ( ale niedużo ).
Aha, i dziele przez wszystkie mniejsze od połowy, bo szczerze mówiąc, nie umiałem podlinkować od biblioteki math.

s_w_ir

28.12.2003, 21:08:36

Z bratem opracowaliśmy że każda liczba nie pierwsza powyżej 10 składa się z jednej z "CZTERECH MAGICZNYCH LICZB: 2 3 5 7", a dokładniej z mnożenia czegoś przez magiczną i na tej podstawie napisaliśmy:[php:1:8e5355715d]<?php
$liczba = 67; //dowolna liczba
if($liczba!=1){
if (($liczba == 2 || $liczba == 3 || $liczba == 5 || $liczba == 7) || ($liczba % 2 != 0 && $liczba % 3 != 0 && $liczba % 5 != 0 && $liczba % 7 != 0))
{
echo "dana liczba jest liczba pierwszan";
}

else
{
echo "badana liczba nie jest liczba pierwszan";
}
}
else echo "badana liczba nie jest liczba pierwszan";
?>[/php:1:8e5355715d]
Chyba to nie obciąża aż tak pamięci?

FiDO

29.12.2003, 16:25:46

Cytat

Z bratem opracowaliśmy że każda liczba nie pierwsza powyżej 10 składa się z jednej z "CZTERECH MAGICZNYCH LICZB: 2 3 5 7", a dokładniej z mnożenia czegoś przez magiczną

Niestety to jest zbyt proste, zeby bylo prawdziwe

Sprawdz chocby liczbe 121, Wasz algorytm stwierdza, ze jest pierwsza, a 121 % 11 = 0. Przykladow mozna by mnozyc...

s_w_ir

29.12.2003, 19:19:49

No to teraz dopiero się fatalnie poczułem. widać jeszcze mam za wąski umysł żeby takie banały przewidywać. Pozdro.

Cudi

29.12.2003, 19:44:43

Tak jak napisałem można skorzystać z metody sita Eratostenesa, która jest dosyć wydajna, a pozwala ze zboiru liczb pozbyć sie wszystkich liczb nie-pierwszych. Nie będe tego opisywał, tylko dam odnośnik do strony gdzie jest to wyjaśnione, jest też kodzik źródlowy dla pascala:
:arrow: http://mpp.qs.pl/XAlgorytmy/AlgPierwsze.html
Oczywiście jest to troche okręzna metoda jeśli chcemy tylko sprawdzić czy dana liczba jest pierwsza, ale zawsze jest to metoda działająca

FiDO

29.12.2003, 20:19:03

Sa wydajne algrgorytmy na sprawdzanie (a przynajmniej losowanie ) duzych (bardzo...) liczb, bo przeciez na tym polega np. RSA, potrzebne sa tam spore liczby pierwsze, ale jak sie nazywa algorytm je losujacy to nie mam zielonego pojecia..

Cudi

29.12.2003, 20:35:10

Niom, niestety masz racje. Przepisałem algorytm z podanej strony na php:
[php:1:cf773fee3d]<?php
$intX = 10000; // ilosc liczb do przecedzenia przez sito
$arrPrimes = range( 1, $intX );

for( $i = 2; $i <= $intX; $i++ )
{
$z = 2;

while( $i * $z <= $intX )
{
unset( $arrPrimes[ array_search( ( $i * $z ), $arrPrimes ) ] );
$z++;
}
}
?>[/php:1:cf773fee3d]
I niestety dla 10000 liczb pierwszych czas wynosi ok. 20 sekund

Ale jeśli chcemy wypisac tylko określoną ilość liczb pierwszych to taki czas jest chyba zadowalający

milosh

29.12.2003, 23:50:23

Witam,
Zainteresowała mnie ta dyskusja, wiec postanowilem napisac cos i spłodziłem to w Pythonie (www.python.org.pl)

Kod

#Tester liczb pierwszych

spr = []

pierw =[1,2,3,5,7,11]

num = input('Podaj liczbe:')

for x in range(2,12):

    spr.append(num%x)

print spr

a = spr[0]+spr[1]+spr[2]+spr[3]+spr[4]+spr[5]+spr[6]+spr[7]+spr[8]+spr[9]

if num in pierw or a != 0:

    print num, 'to l. pierwsza'

else:

    print num, 'to nie l.pierwsza'

Nie jestem pewien, jak to będzie działało na większych liczbach, więc prosiłbym o test. Jeśli coś jest niejasne, chętnie wyjaśnię

Pozdr.

s_w_ir

30.12.2003, 11:23:48

To ja mam na 100% pewny kod i na 100% nie wydajny przy dużych liczbach i na który chyba każdy z was wpadł:[php:1:4ea04ac18a]<?php
$liczba=105;//dowolna liczba
if($liczba>=2){
for($i=2;$i<$liczba;$i++){
if($liczba % $i==0){ echo "Liczba $liczba dzieli się przez $i<br>";
$d++;}
}
if($d==0) echo "Liczba jest Pierwsza";
else {
$liczba2=$liczba-1;
echo "Liczba nie jest pierwsza, ponieważ dzieli się przez $d liczb(y) z przedziału (2, $liczba2)";
}
}
else echo "Liczba nie jest pierwsza";
?>[/php:1:4ea04ac18a]
edit:
Jednak można to skrócić dodając break jak tylko znajdzie się liczba która daje resztę 0 z dzielenia

FiDO

30.12.2003, 17:54:08

Teraz to sie nie popisales

W tej metodzie (typowy brute-force bez optymalizacji) masz N - 2 iteracji petli, a w metodzie z pierwiastkiem (ktora podalem na poczatku) jest juz sqrt(N) - 2 iteracji, roznica jest niebanalna, choc i tak obie metody sa wolne (dla duzych liczb).

milosh

30.12.2003, 19:53:43

Cytat

Widzisz ale tu nie wykluczasz brak licz pseudopierwszych

Niestety zdałem sobie sprawę z tego dopiero dziś, więc poprawiłem kod na coś takiego:

Kod

# Tester Liczb Pierwszych

spr = []

lp=[1,2,3,5,7]

num=666

while num != 0:

    num = input('Podaj liczbe:')

    if num < 0:

        continue

    for x in range(2,11):

        spr.append(num%x)

    print spr

    if round(num**0.5) != num**0.5 and 0 not in spr or num in lp:

        print num, 'to l. pierwsza'

        spr=[]

    else:

        print num, 'to nie l. pierwsza'

        spr=[]

print 'thx'

Teraz chyba działa, przynajmniej tak wynika z moich testów. Liczba wyjątków (o ile takie istnieją) jest chyba bardziej ograniczona.
Pozdr

dr_bonzo

21.05.2004, 21:47:24

Cytat

To jakos tak bylo, ze: kazda liczbe calkowita da sie zapisac w postaci iloczynu liczb pierwszych.
Np:
39 = 3 * 13
14 = 2 * 7
210 = 2 * 3 * 5 * 7
5610 = 2 * 5 * 11 * 17

13 = 1 * 13
7 = 1 * 7

Jabol

21.05.2004, 22:13:46

285311670611=11*11
niestety, nie zadziałało

PMadej

22.05.2004, 00:33:31

przeciez to nie sa liczby pierwsze:
39 = 3 * 13
14 = 2 * 7
210 = 2 * 3 * 5 * 7
5610 = 2 * 5 * 11 * 17

liczba pierwsza dzieli sie przez sama siebie i przez 1 ... wiec wszystko co mnozysz przez cos innego niz 1 odpada

te tak:
13 = 1 * 13
7 = 1 * 7

matys

22.05.2004, 09:18:51

Ja napisałem w C++ program, który sprawdza, czy podana przez użytkownika liczba, jest liczbą pierwszą:

Kod

#include <iostream>

#include <stdlib.h>

using namespace std;

int main()

{

    int a, b, c, d;

    do

    {

    cout << "Podaj liczbe: ";

    cin >> a;

    b=2;

    do

        {

                c=a%b;

                b=b+1;

        }

    while(c!=0 && b<a);

    if((b<a) || (a==0))

    cout << "Liczba nie jest pierwsza.n";

    else

    cout << "Liczba jest pierwsza.n";

    cout << "1-dla kontynuacji, 2-dla wyjscian";

    cin >> d;

  }while(d==1);

  system("PAUSE");

  return 0;

}

Cudi

22.05.2004, 09:50:25

PMadej: Nie zrozumiałeś go, idź przeczytaj jeszcze raz co napisał

Cytat

To jakos tak bylo, ze: kazda liczbe calkowita da sie zapisac w postaci iloczynu liczb pierwszych.

Każdą liczbe całkowitą, więc nie jest powiedziane że po lewej stronie musi być liczba pierwsza. Tylko ze nie wiem jak to można wykorzystać przy sprawdzaniu czy dana liczba jest liczbą pierwszą

dr_bonzo

22.05.2004, 09:52:38

Cytat

285311670611=11*11
niestety, nie zadziałało

tzn. nie dalo sie rozlozyc na czynniki pierwsze?

Cytat

przeciez to nie sa liczby pierwsze:
39 = 3 * 13
14 = 2 * 7
210 = 2 * 3 * 5 * 7
5610 = 2 * 5 * 11 * 17
(...)

Zgadza sie -- nie sa to liczby pierwsze, ale prosze czytaj uwazniej --

Cytat

To jakos tak bylo, ze: kazda liczbe calkowita da sie zapisac w postaci iloczynu liczb pierwszych.

Jabol

22.05.2004, 13:06:00

ale zauważ, że ta liczba którą podałem też da się rozłożyć na liczby pierwsze, ale tylko jedenastki, bo zakres liczb pierwszych jest szerszy od podanego przez Ciebie.

aha, i to nie było 11 * 11, tylko 11 ^ 11, ale prawidłowość pozostaje taka sama (121 też nie rozłożysz na czynniki pierwsze w przedziale 0 < n < 10).

raf2001

22.05.2004, 13:59:27

Witam!
Wtrące się do rozmowy (jeżeli to co powiem już się powtórzylo to mnie niewincie niejestem w stanie śledzić przebiegu całej rozmowy)
Liczby pierwsze można posazukiwać przez wzór 2^n-1 gdzie n-liczba pierwsza. Mój pomysl (dlatego zwracam się do was jest chyba prosty, ale niwiem jak go rozpisać). Otóz skrypt na poczatku przeszukuje liczbe pierwszą z podanego zakresu. Poźniej sprawdzony zostaje wynicz czy n jest liczbą pierwszą i zostaje wykożystany wzór 2^n-1 i znowu zostaje sprawdzony wynicz czy liczba jest liczbą pierwszą i uzyskany wynik zostaje znowu podstawiony do wzoru (zrobić to można na pętli, tylko jak).Funkcja oczywiście musiała by mieć określone ile powtórzeń ma zostać wykonanych. Czy jest to możliwe do zrealizowania?

To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.