Sprawdzanie pierwszości dziesięciocyfrowych liczb pierwszych

napisałem program, ale wydaje mi się że działa za wolno przy tak dużych liczbach.

 #include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int unsigned long long pierwsza;
    bool czy_pierwsza=true;
    cin>>pierwsza;
     if(pierwsza%2!=0){
            for(int i=3;i<=sqrt(pierwsza);i=i+2)
            {
                if(pierwsza%i==0)
                {
                    czy_pierwsza=false;
                    break;
                }
            }
            if(czy_pierwsza==true)
               cout<<"liczba pierwsza";
             else
            cout<<"to nie jest liczba pierwsza"<<endl;

            }
    else
            cout<<"to nie jest liczba pierwsza"<<endl;
    return 0;
}

To nie zadziała, sqrt(pierwsza) to za mało dla zakresu [3.10000] ( a co dopiero dla 10-cyfrowych liczb), sqrt(pierwsza)*2 będzie ok.
I czemu i=i+2?

Nie jestem ekspertem z C++, ale chyba w kazdym obiegu petli liczysz pierwiastek z tej wczytanej liczby. Ona sie nie zmienia w kolejnych iteracjach, wiec wystarczy, ze pierwiastek policzysz raz i potem normalnie sprawdzisz tylko wartosc

jak przyspieszyć uzupełnianie sita Eratostenesa do tak dużej liczby jaka jest 9 999 999 999

Niezbyt jest jak - po prostu sito Erastostenesa jest wolne jako algorytm sam w sobie :P

Może podam treść zadania, ponieważ cały czas program działa za wolno. W ciągu n od lugosci n<10000 znakow ukryte są liczby pierwsze o długości od 3 do 9 znaków policz ile liczb pierwszych zawiera ciąg. Napisałem taki kod, ale jest on stanowczo za wolny.

#include <iostream>
#include<cmath>
#include<sstream>

using namespace std;

const int n = 999999999;

bool numbersTable[n ]; // tablica o indeksach od 0 do 999999999 

int main()
{
    for (int i = 2; i*i <= n; i++ ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie są liczbami pierwszymi
    {
        if (numbersTable[i] == true) // jeżeli dana liczba jest już wykreślona
            continue; // to przejdź do kolejnej
        for (int j = 2*i ; j <= n; j += i) // przejdź od liczby 2*i do n przesuwając się o i
            numbersTable[j] = true; // i każdą z nich usuwaj ze zbioru
    }

    string liczba,tmp;
    bool czy_pierwsza=true;
    int unsigned long long b,pierw;
    int licznik=0;
    stringstream ss;
    cin>>liczba;
    for(;liczba.size()!=2;)
    {
        tmp=liczba.substr(0,9);
        ss<<tmp;
        ss>>b;

        ss.clear();

        for(;b>99;)
        {

            if(numbersTable[b]==false)
                licznik++;
            b=b/10;




        }


        liczba.erase(0,1);
    }
        cout<<licznik;
    return 0;
}

 

Jeśli chcesz tylko sprawdzić pierwszość takich liczb, to są lepsze sposoby: https://pl.wikipedia.org/wiki/Test_Millera-Rabina

w moim kodzie nie ma żadnych błędów, które będą powodowały złe wyniki?? dodam tu jeszcze ze limit czasu jednego wykonania kodu wynosi 0,1 sek

Test_Millera-Rabina zmieniony kod:

#include <iostream>
#include <cstring>
#include <cstdlib>
#include<sstream>
#define ll long long
using namespace std;


ll mulmod(ll a, ll b, ll mod)
{
    ll x = 0,y = a % mod;
    while (b > 0)
    {
        if (b % 2 == 1)
        {
            x = (x + y) % mod;
        }
        y = (y * 2) % mod;
        b /= 2;
    }
    return x % mod;
}

ll modulo(ll base, ll exponent, ll mod)
{
    ll x = 1;
    ll y = base;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            x = (x * y) % mod;
        y = (y * y) % mod;
        exponent = exponent / 2;
    }
    return x % mod;
}


bool Miller(ll p,int iteration)
{
    if (p < 2)
    {
        return false;
    }
    if (p != 2 && p % 2==0)
    {
        return false;
    }
    ll s = p - 1;
    while (s % 2 == 0)
    {
        s /= 2;
    }
    for (int i = 0; i < iteration; i++)
    {
        ll a = rand() % (p - 1) + 1, temp = s;
        ll mod = modulo(a, temp, p);
        while (temp != p - 1 && mod != 1 && mod != p - 1)
        {
            mod = mulmod(mod, mod, p);
            temp *= 2;
        }
        if (mod != p - 1 && temp % 2 == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
     int iteration = 5,dl;
    ll num;
    int licznik=0;
    string b,tmp;
    stringstream ss;
    cin>>b;
     for(;b.size()!=2;)
    {
        tmp=b.substr(0,9);
        ss<<tmp;
        ss>>num;

        ss.clear();

        for(;num>99;)
        {


            if (Miller(num, iteration))
                licznik++;
            num=num/10;




        }


        b.erase(0,1);
    }
                cout<<licznik;

    return 0;
}

tyle, że na wiki jest napisane, że jeśli wybierzesz konkretne wartości a to test jest deterministyczny do pewnej (bardzo dużej) wartości liczby p.
Na dodatek jest napisane, by częściowo testować sitem w celu optymalizacji.

1. większość liczb jest złożona. Sprawdzając dzielenie danej liczby przez kilka początkowych liczb pierwszych np: (2,) 3, 5, 7, 11. szybko odrzucasz sporą cześć liczb złożonych niewielkim kosztem, co ogólnie przyspiesza test (duży zysk na liczbach złożonych, mała strata na liczbach pierwszych).
2. jest kilka przepisów na dobór liczby a, ale jeśli się dokładniej wczytasz w wiki angielskie to zauważysz, że wszystkie przepisy z wiki polskiego są wymienione w wersji angielskiej, więc nie rozumiem czemu czepiasz się różnic!
3. ty masz liczbę 10 cyfrową, ergo wszystkie testowane przez ciebie liczby są mniejsze niż 10^10, czyli z przepisów dostarczonych na wiki powinieneś wybrać jeden z tych dwóch:

wiki napisał(a)

if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803;
if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11

Pierwszy testujesz tylko dla czterech wartości a, ale o dużej liczbie bitów 1, w drugim testujesz dla 5 liczb a, ale wszystkie są dość małe i mają mało bitów 1 więc test może być szybszy. Najlepiej sprawdzić to doświadczalnie.

nadal jest cos zle ;x

 #include <iostream>
#include <cstdlib>
#include <time.h>
#include<sstream>

using namespace std;


const int n = 11;

bool numbersTable[n + 1];

void sito()
{
    for (int i = 2; i*i <= n; i++ )
    {
        if (numbersTable[i] == true)
            continue;
        for (int j = 2*i ; j <= n; j += i)
            numbersTable[j] = true;
    }

//        if (numbersTable[i] == false)



}
// 64 bitowy generator pseudolosowy
//---------------------------------


// Funkcja mnoży a i b mod n
//--------------------------
int unsigned long long MnozModulo(int unsigned long long a, int unsigned long long b, int unsigned long long n)
{
  int unsigned long long m,w;

  w = 0;
  for(m = 1; m; m <<= 1)
  {
    if(b & m) w = (w + a) % n;
    a = (a << 1) % n;
  }
  return w;
}

// Funkcja oblicza a^e mod n
//--------------------------
int unsigned long long PotegujModulo(int unsigned long long a, int unsigned long long e, int unsigned long long n)
{
  int unsigned long long m,p,w;

  p = a; w = 1;
  for(m = 1; m; m <<= 1)
  {
    if(e & m) w = MnozModulo(w,p,n);
    p = MnozModulo(p,p,n);
  }
  return w;
}

int main()
{
    stringstream ss;
    sito();
    int unsigned long long a,d,p,x;
    int i,j,s,licznik=0;
    bool t;
    string b,tmp;
    cin>>b;
    for(;b.size()!=1;)
    {
        tmp=b.substr(0,9);
        ss<<tmp;
        ss>>p;
        ss.clear();
        for(;p>99;){
          s = 0;
          for(d = p - 1; d % 2 == 0; s++) d /= 2;
          t = true;
           for (int i = 2; i <= n; i++)
                if (numbersTable[i] == false) {
            a =i;

            x = PotegujModulo(a,d,p);
            if((x == 1) || (x == p - 1)) continue;
            for(j = 1; (j < s) && (x != p - 1); j++)
            {
              x = MnozModulo(x,x,p);
              if(x == 1)
              {
                t = false; break;
              }
            }
            if(!t) break;
            if(x != p - 1)
            {
              t = false; break;
            }

          }
          if(t)
            licznik++;
          p=p/10;
        }
        b.erase(0,1);
    }
    cout<<licznik;
  return 0;
}