Liczby pierwsze w locie

Witam,
poszukuję algorytmu, który będzie generował liczby pierwsze. Problem w tym, że mam znaleźć liczby pierwszy mniejsze od jakieś liczby i zwracać je w procedurze zwrocNastepną - zwraca następną liczbę pierwszą. Jak można to zrobić. Szukanie za każdym razem większej liczby pierwszej od poprzedniej nie ma sensu, nie mogę wygenerować na początku wszystkich liczb i zapisać do tablicy, więc sito Eratostenesa i inne algorytmy się chyba nie zdzadzą. Z góry dzięki.

po zamknięciu kodu w obiekt możesz trzymać wszystkie poprzednio znalezione liczby w tablicy, a więc problem spokojnie rozwiązać sitem Eratostenesa.
dla dużych liczb (kilkaset bitów i więcej) istnieją metody probabilistyczne do sprawdzania z pewnym prawdopodobieństwem (np. 1/2 albo 1/4) czy liczba jest/nie jest liczbą pierwszą, po sprawdzeniu np. 64 razy masz p-wo 2^-64, że liczba będzie błędnie zakwalifikowana jako pierwsza. algorytmów takich używa się np. w RSA. kiedyś implementowałem jeden, ale to było ze sto lat temu.

Czyli funkcja zwrocNastepna() ma przyjmowac jako parametr, liczbę pierwszą i zwracać następna liczbe pierwszą w kolejności?

Nie mogę użyć tablicy do wcześniejszego generowania liczb. Trzeba je generować na bieżąco.
Metoda zwrocNastepna() nie musi przyjmować żadnego parametru. Mogę zadeklarować zmienną, która pamięta ostatnią znalezioną.

Więc czy nie wystarczy Ci taka funkcja i petla?

bool Prime(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)
            return false;
    }
    return true;
}

Taką prymitywną funkcję sama wymyśliłam. Szukam czegoś optymalnego.

uwierz, szukałam, ale pomysły się wyczerpały.

Nie jest to najszybsze rozwiązanie ale może Ci coś pomoże:

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    //ios_base::sync_with_stdio(0);
    int p[]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    int n,t,i,j,x;
    bool r;
    cin>>n;

    for(i=0; i<n; i++)
    {
        cin>>t;
        if(t==1) r=false;
        else if(t<4) r=true;
        else if(t%2==0) r=false;
        else
        {
            r=true;
            x=sqrt(t);
            for(j=0; p[j]<=x; j++)
            {
                if(t%p[j]==0)
                {
                    r=false;
                    break;
                }
            }
        }
        cout<< (r ? "TAK\n" : "NIE\n");
    }
    return 0;
}

dla przedziału (0;10000);

class PrimesGenerator
{
    private int lastNumber;

    public int GetNext()
    {
        while (!this.IsPrime(this.lastNumber))
            this.lastNumber++;

        return this.lastNumber++;
    }

    private bool IsPrime(int x)
    {
        if (x <= 1) return false;
        if (x <= 3) return true;
        if (x % 2 == 0 || x % 3 == 0) return false;
        for (int i = 5; (i * i) <= x; i += 6)
        {
            if (x % i == 0) return false;
            if (x % (i + 2) == 0) return false;
        }
        return true;
    }
}

Ja bym taki generator dla intów zrobił inaczej. Na początku użyłbym sita dla liczb pierwszych mniejszych niż 2^16. Wynikowe liczby pierwsze z tego segment przechowywałbym cały czas. Gdy wszystkie z nich zostaną wyczerpane, to można ich użyć do zrobienia kolejnego sita, o tej samej wielkości, tylko, że przesuniętego. Podobnie dla kolejnych segmentów, aż do końca inta (dla każdego segmentu wystarczą tylko te pierwsze liczby). Taki algorytm jest bardziej uniwersalny, ponieważ maksymalny czas wywołania zapytania generatora jest sensowny oraz duża ilość wywołań jest o wiele szybsza, niż przy niestosowaniu sita.

agnieszkar1200 napisał(a)

uwierz, szukałam, ale pomysły się wyczerpały.
napisałem Ci o algorytmach probabilistycznych, jak widzę czytasz bez zrozumienia albo masz sklerozę. użyj algorytmu rabina-millera, jest dość łatwy do zaimplementowania i dość szybki. link znajdziesz na stronie podanej w komentarzu przez mto9.

ok, dzięki. Jak nie da się przerobić żadnych algorytmów tablicowych, to poczytam o tych.

typedef unsigned int uint;

uint next(uint c){
	//static uint c=1; //1+30n, 7+30n, 11+30n, 13+30n, 17+30n, 19+30n, 23+30n, 29+30n
	//              0 1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
	const uint t[]={1,6,5,4,3,2,1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 2};
	const uint m[]={2,2,3,5,5,7,7,11,11,11,11,13,13,17,17,17,16,19,19,23,23,23,23,29,29,29,29,29,29,31};

	if( c<30 ) return c = m[c];
	while( 1 ){ uint d;
		c += t[c%30];
		for( d=7; d*d<=c; d+=6 )
			if( c%d==0 || c%(d+4)==0 ) break;
		if( d*d>c ) return c; }
	return c;
}

int main(void){
	uint i,j;
	j=next(1000000);
	for(i=0; i<100000; i++ )
		j=next(j);
	return ! printf("\n%u", j); } 

Niby lżejsze, ale tylko trochę,
jakoś tak by to trzeba robić

Zupełnie dziwi mnie, że prawie wszyscy piszą tutaj kody napałowe...

wśród liczb postaci 30n+k tylko osiem nie dzieli się przez 2, 3 lub 5
m[] to oczywiście A007918, ale od zera cholera
a o t[] Sloane's jakoś nie wspomina

mam wrażenie, że c%30 da się wyrzucić przed while, tylko jakby to zgrabnie zapisać?