liczby pierwsze Opcje

[Jabol]

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

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.

[Jabol]

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.