Jak usprawnić ten kod

0

Tak jak w temacie, oceńcie i poprawcie to co trzeba. Zadanie pochodzi ze spoja i nazywa się "Dyzio":

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

int t, p1, p2, il;

void sito(bool *tab, unsigned int n)
{
	for (int i = 2; i*i <= n; i++)
	{
		if (!tab[i])
			for (int j = i*i; j <= n; j += i)
				tab[j] = 1;
	}
}

int main()
{
	const int n = 10000000;
	bool *tab;

	cin >> t;

	for (int k = 0; k < t; k++)
	{
		il = 0;
		cin >> p1 >> p2;

		tab = new bool[n+1];

		for (int i = 2; i <= n; i++)
			tab[i] = 0;

		sito(tab, n);

		for (int i = p1; i <= p2; i++)
			if (!tab[i])
				il++;

		cout << il << endl;
	}
	delete[]tab;
	return 0;
} 
5
  1. zmienne globalne
  2. bezsensnowne zmienne
  3. uzycie golego new. Poczytaj o RAII (w szczegolnosci o smart pointerach) [tak wiem, ze to spoj i sie pisze kod glownie zeby szybko dzialal, ale...]
  4. nie ma potrzeby uzywac wskaznikow
  5. brakuje const-correctness
  6. endl nie sluzy do nowej linii
  7. masz wyciek pamieci, ilosc delete powinna byc taka sama jak ilosc new (a masz wyciek przez to ze nie uzywasz smart pointerow)

A optymalizacyjnie to nie wiem bo nie ma tresci zadania (nawet nie podales linka)

4
  1. masz wycieki pamięci
  2. stosujesz nagie new i delete zamiast poprawnie pisać w C++
  3. alokujesz tablicę i liczysz sito t razy (po co? Inne liczby pierwsze dla każdej iteracji wychodzą?)
0

Co jeszcze zmienić?:

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

void sito(bool *tab, unsigned int n)
{
	for (int i = 2; i*i <= n; i++)
	{
		if (!tab[i])
			for (int j = i*i; j <= n; j += i)
				tab[j] = 1;
	}
}

int main()
{
	const int n = 10000000;
	int t, p1, p2, il;
	bool *tab;

	tab = new bool[n + 1];

	for (int i = 2; i <= n; i++)
		tab[i] = 0;

	sito(tab, n);
	cin >> t;

	for (int k = 0; k < t; k++)
	{
		il = 0;
		cin >> p1 >> p2;

		for (int i = p1; i <= p2; i++)
			if (!tab[i])
				il++;

		cout << il << endl;
	}
	delete[]tab;
	return 0;
} 
0

Dlaczego niby wskaźniki są niepotrzebne?

2

bo

  1. smart pointery i jest make_unique
  2. std::vector
0

A co znaczy nagi new i delete?

1

nie czytales tego co wypunktowalem ja ani kq. Zacznij czytac po kolei a nie wyrywkowo to bedzie jasniejsze. Chodzi o to ze powinienes uzyc smart pointerow

0

Jeśli to jest sito erastotenesa i działa za wolno, to poczytaj o sicie atkina.

Co ten program ma dać na wyjściu?
Pozdrawiam

2
Fastkonrad napisał(a):

A co znaczy nagi new i delete?
Użyłeś new i delete bezpośrednio w swoim kodzie. Tak się nie robi, to nie 1998 był prawie 20 lat temu.

1

Program nie jest zbyt estetyczny ani przejrzyście zakodowany, zawiera new i delete, ale to wszystko pozostawiam Tobie do dokończenia ;-)

Tą metodą nie uzyskasz dużo szybszego czasu, na dobrym kompie może da się w 50s znaleźć początkowe 10mln liczb pierwszych.
Jak już pisałem w komentarzu, jeśli te czasy są zbyt długie dla Ciebie, to byś musiał użyć sita atkina, albo jakiś testów probabilistycznych.

Pozdrawiam

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>

typedef unsigned long long ulong;


int main(int argc, char *argv[])
{
    const time_t start = time(NULL);
    const ulong N = 10000000;

    ulong *const sito = new ulong[N];
    unsigned i=0;
    ulong j=3;

    sito[i++] = 2;

    while( i<N ) {
        const ulong k = (ulong)sqrt(j);
        unsigned l=0;
        while( sito[l] <= k && j % sito[l] )
            l++;
        if( sito[l] > k )
            sito[i++] = j;
        j++;
    }

    for( unsigned k=N-100 < 0 ? 0 : N-100 ; k<i ; k++ )
        printf("%u %llu\n" , k+1 , sito[k] );

    delete[] sito;

    printf("%ds\n",(int)(time(NULL)-start));

    return 0;
}

0

Działa zbyt wolno bo aplikujesz sito dla n = 10**7 niezależnie od p1 i p2</code>. Nie chcę mi się szukać teraz treści zadania, ale nie zdziwiłbym się gdyby w zadaniu było zalożenie, że np. <code>p2 - p1 <= 10**5 czyli innymi słowy p1 i p2 są o siebie oddalone o co najwyżej 100k (czyli ten przedział dla którego musimy obliczyć ilość liczb pierwszych jest znacznie niż dla którego Ty liczysz) :P

2

Jeżeli chodzi o wydajność, to są dwie sprawy.

  1. W zadaniu Dyzio (http://pl.spoj.com/problems/DYZIO2) dane wejściowe są z zakresu od 2 do 106, a Ty tworzysz tablicę o wielkości 107.
  2. Nie trzeba zliczać liczb pierwszych dla każdej pary danych wejściowych. Wystarczy, że na początku zsumujesz ilość wystąpień liczb pierwszych i zapiszesz je w tej tablicy tak, że tab[i] będzie zawierać ilość liczb pierwszych <= i. Potem jednym odejmowaniem można obliczyć ilość liczb pierwszych występujących w zakresie.
#include <iostream>
#include <cstdlib>

using namespace std;

void sito(int *tab, unsigned int n)
{
	for (int i = 2; i*i <= n; i++)
	{
		if (!tab[i])
			for (int j = i*i; j <= n; j += i)
				tab[j] = 1;
	}
}

int main()
{
	const int n = 1000000;
	int t, p1, p2;
	int *tab;

	tab = new int[n + 1];

	for (int i = 0; i <= n; i++)
		tab[i] = 0;

	sito(tab, n);
	cin >> t;

	int s = 0;
	for (int i = 2; i <= n; i++)
	{
		s += !tab[i];
		tab[i] = s;
	}

	for (int k = 0; k < t; k++)
	{
		cin >> p1 >> p2;
		cout << tab[p2] - tab[p1 - 1] << endl;
	}

	delete[]tab;
	return 0;
}
0

@artur_bredzki Jakiej znowuż zgodności? :O - n0name_l

n0name_l, rozpoznaj czy to jest program w C czy w C++ :)

int main() {
return 0;
}

0
Pebal napisał(a):

void sito(int tab, unsigned int n)
{
for (int i = 2; i
i <= n; i++)
{
if (!tab[i])
for (int j = i*i; j <= n; j += i)
tab[j] = 1;
}
}

Czy nie będzie szybciej jeśli zapamięta się w tablicy liczby pierwsze?

Pozdrawiam

0
artur_bredzki napisał(a):

Czy nie będzie szybciej jeśli zapamięta się w tablicy liczby pierwsze?

Nie bardzo rozumiem, masz na myśli umieszczenie ich w kodzie programu?

0
Pebal napisał(a):

Nie bardzo rozumiem, masz na myśli umieszczenie ich w kodzie programu?

W kodzie programu wystarczy umieścić jedną liczbę pierwszą, konkretnie liczbę 2

Najpierw w tablicy przechowujemy tę dwójkę:

sito[0] = 2;
Dzięki temu program już wie, że 2 to liczba pierwsza.
Trzeba sprawdzić kolejne liczby począwszy od 3,4,5,6, aż do N

Twierdzenie:
Jeśli liczba X nie jest pierwsza, to dzieli się przez jakąś liczbę
pierwszą mniejszą lub równą od pierwiastka z X.

Pierwiastek z 3 po zaokrągleniu w dól to 1. Liczby pierwsze
mamy w tablicy sito. Więc sprawdzamy resztę z dzielenia
dla liczb z sita mniejszych lub równych 1. W sicie jest tylko
dwójka, więc nie ma liczby która by dzieliła 3 bez reszty.
Zatem dodajemy do sita liczbę 3
sito[1] = 3;
potem sprawdzamy w ten sam sposób dla liczby 4.
Pierwiastek z 4 to dwa
w sicie jest liczba 2, która dzieli 4, więc 4 nie jest liczbą
pierwszą. Potem dla kolejnych liczb tak samo.

Tak działa ten program który wyżej wkleiłem, a która metoda
jest szybsza, to nie mam bladego pojęcia. Twoja metoda
zużywa więcej pamięci, a moja używa wolnego sprawdzania
podzielności. Dla dużych zakresów Twoja metoda na
pewno będzie gorsza, a dla małych to nie wiem.

Pozdrawiam

0
artur_bredzki napisał(a):

W kodzie programu wystarczy umieścić jedną liczbę pierwszą, konkretnie liczbę 2
...

Dla tablicy 107 Twój kod wyznacza liczby pierwsze 10 razy wolniej.
Pierwotny kod, wyszukując liczby pierwsze, wykonuje ok. 32853213 operacji na tablicy 107 (odczyt, porównanie, zapis) i 447 mnożeń (z tych bardziej złożonych operacji). Wykonuje się u mnie w czasie 104ms.
Twój kod wykonuje 306809479 operacji na tablicy 664579 elementów, 276809511 dzieleń i 9999989 pierwiastkowań. Zajmuje mu to 1080ms.

0

Zajmuje mu to 1080ms.

Coś mi się nie zgadza, chyba niemożliwe. To by oznaczało, że uruchamiasz go na 23 razy szybszym komputerze od mojego.
U mnie dla tablicy 10^7 działa 235 sekund. Wykonujje 179424671 pierwiastkowań i 948214104 reszt z
dzielenia. Znajduje 10^7 liczb pierwszych. Największa liczba pierwsza wynosi 179424673. Oznacza to,
ze byś musiał tamten program ruchomić z tablicą o rozmiarze 179424673, aby uzyskać taki sam
efekt jaki mój uzyskuje na tablicy 10^7. Wtedy zmierz czasy :)

Pozdrawiam

0
artur_bredzki napisał(a):

Zajmuje mu to 1080ms.

Coś mi się nie zgadza, chyba niemożliwe. To by oznaczało, że uruchamiasz go na 23 razy szybszym komputerze od mojego.

Nie zgadza Ci się, bo powinieneś uruchomić swój kod dla tablicy o wielkości 664579 elementów. Dokładnie tyle liczb pierwszych jest mniejszych od 107. Ja uruchamiałem Twój kod właśnie dla takiej tablicy.

0

A zróbmy tak jak jest w zadaniu, że na standardowe wejście podaje się pary min i max.
Zmniejszyłem też typ na 32 bitowy, działa dzięki temu sporo szybciej.

U mnie dla
4
0 10000000
10000000 20000000
30000000 40000000
0 40000000

13.512 sekundy

#include <cmath>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <cstdlib>

typedef unsigned prime_t;
typedef unsigned utyp;

static bool isPrime( const std::vector<prime_t> &v , const prime_t p ) {
    const prime_t sp = sqrt(p);
    for( utyp i=0 ; v[i] <= sp ; i++ )
        if( p % v[i] == 0 )
            return false;
    return true;
}

static void appendPrimes( std::vector<prime_t> &v , prime_t max ) {
    if( v.size() == 0 )
        v.push_back(2);
    prime_t i = v.back();
    while( i++ < max ) {
        if( isPrime( v , i ) )
            v.push_back( i );
    }
}


static utyp countPrimies(const std::vector<prime_t> &v , const prime_t min, const prime_t max ) {
    const std::vector<prime_t>::const_iterator imin = std::lower_bound( v.begin() , v.end() , min );
    const std::vector<prime_t>::const_iterator imax = std::lower_bound( v.begin() , v.end() , max );
    return imax - imin + (imax != v.end() && *imax == max);
}


int main(int argc, char *argv[])
{
    std::vector<prime_t> v;
    std::string line;

    std::getline(std::cin,line) ;
    while( std::getline(std::cin,line) ) {
        prime_t min, max;
        std::stringstream ss;
        ss << line;
        ss >> min >> max;
        appendPrimes( v , max );
        std::cout << min << ' ' << max << ' ' << countPrimies(v,min,max) << '\n';
    }

    return 0;

}

Pozdrawiam

0

Twój algorytm: 6.539s
Mój algorytm: 0.511s

[Edit]
Udało mi się zejść do 143ms.

1

Kod poniżej, czas u mnie 89ms.

#include <iostream>
#include <vector>
 
typedef unsigned uint;
typedef std::pair<uint, uint> Range;
 
struct EratosthenesSieve
{
    EratosthenesSieve(uint size) : buffer_((size + 7) / 8), size_(size) 
    {
        std::fill(buffer_.begin(), buffer_.end(), 0x55);
        buffer_[0] = 0x53;
 
        for (uint i = 3; i*i < size; i += 2)
            if (isPrime(i))
                for (uint j = i*i; j < size; j += i*2)
                    buffer_[j / 8] |= 1 << (j & 7);
    }
 
    bool isPrime(uint i) const {
        return (buffer_[i / 8] & 1 << (i & 7)) == 0; 
    }
 
    uint size() const {
        return size_; 
    }
 
private:
    std::vector<unsigned char> buffer_;
    const uint size_;
};
 
int main()
{
    std::vector<Range> ranges;
    uint count, first, second;
    uint max = 0, s = 1;
 
    std::cin >> count;
    while (count--)
    {
        std::cin >> first >> second;
        max = std::max(second, max);
        ranges.emplace_back<Range>({first, second});
    }
 
    EratosthenesSieve numbers(max + 1);
    std::vector<uint> cprimes(max / 2 + 1);
 
    for (uint i = 1; i <= max; i += 2)
        cprimes[i / 2] = s += numbers.isPrime(i);
 
    for (auto range : ranges)
    {
        int c1 = range.first > 1 ? cprimes[(range.first - 1) / 2] : 0;
        int c2 = range.second > 1 ? cprimes[(range.second - 1) / 2] : 0;
        std::cout << c2 - c1 + numbers.isPrime(range.first) << "\n";
    }
 
    return 0;
}
0

Porównałem jeszcze sito erastotenesa z sitem atkina i sito atkina jest około 2 razy wolniejsze od sita erastotenesa, co mnie
bardzo dziwi. Może wynika to z kiepskiej implementacji sita atkina, albo przewaga sita atkina ujawnia się dopiero na większych
zakresach liczb - nie wiem. Lepiej zaimplementować nie umiem sita atkina. Poniżej kod:

#include <cmath>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cstring>

#include <iostream>
#include <vector>

//#define ERASTOTENES
#define ATKIN


#ifdef ERASTOTENES

typedef unsigned uint;
typedef std::pair<uint, uint> Range;

struct EratosthenesSieve
{
    EratosthenesSieve(uint size) : buffer_((size + 7) / 8), size_(size)
    {
        std::fill(buffer_.begin(), buffer_.end(), 0x55);
        buffer_[0] = 0x53;

        for (uint i = 3; i*i < size; i += 2)
            if (isPrime(i))
                for (uint j = i*i; j < size; j += i*2)
                    buffer_[j / 8] |= 1 << (j & 7);
    }

    bool isPrime(uint i) const {
        return (buffer_[i / 8] & 1 << (i & 7)) == 0;
    }

    uint size() const {
        return size_;
    }

private:
    std::vector<unsigned char> buffer_;
    const uint size_;
};

int main()
{
    std::vector<Range> ranges;
    uint count, first, second;
    uint max = 0, s = 1;

    std::cin >> count;
    while (count--)
    {
        std::cin >> first >> second;
        max = std::max(second, max);
        ranges.emplace_back<Range>({first, second});
    }

    EratosthenesSieve numbers(max + 1);
    std::vector<uint> cprimes(max / 2 + 1);

    for (uint i = 1; i <= max; i += 2)
        cprimes[i / 2] = s += numbers.isPrime(i);

    for (auto range : ranges)
    {
        int c1 = range.first > 1 ? cprimes[(range.first - 1) / 2] : 0;
        int c2 = range.second > 1 ? cprimes[(range.second - 1) / 2] : 0;
        std::cout << c2 - c1 + numbers.isPrime(range.first) << "\n";
    }

    return 0;
}

#endif

#ifdef ATKIN


typedef unsigned prime_t;
typedef unsigned utyp;


std::vector<prime_t> genPrime( const prime_t max ){
  const utyp sq = (utyp)(sqrt(max));
  if( sizeof(utyp) != 4 )
      abort();
  utyp *const vv = new utyp[(max+31)/32+1];
  memset( vv , 0 , 4*((max+31)/32+1) );
  for(utyp x1 = 1; x1 <= sq; x1++) {
    const utyp x2 = x1 * x1;
    for(utyp y1 = 1; y1 <= sq; y1++) {
      const utyp y2 = y1 * y1;
      utyp z = (x2 << 2) + y2;
      if((z <= max) && ((z % 12 == 1) || (z % 12 == 5)))
          vv[z>>5] ^= 1u << (z&31);
      z -= x2;
      if((z <= max) && (z % 12 == 7))
          vv[z>>5] ^= 1u << (z&31);
      if(x1 > y1) {
        z -= y2 << 1;
        if((z <= max) && (z % 12 == 11))
            vv[z>>5] ^= 1u << (z&31);
      }
    }
  }
  for(utyp loop = 5; loop <= sq; loop++) {
    if(vv[loop>>5] & (1u<<(loop&31))) {
      const utyp x2 = loop * loop;
      utyp z = x2;
      while(z <= max) {
        vv[z>>5] &= ~(1u<<(z&31));
        z += x2;
      }
    }
  }
  std::vector<prime_t> p;
  p.push_back(2);
  p.push_back(3);
  for(utyp loop = 5; loop <= max; loop++)
    if( vv[loop>>5] & (1u<<(loop&31)) )
        p.push_back(loop);
  delete [] vv;
  return p;
}

static utyp countPrimies(const std::vector<prime_t> &v , const prime_t min, const prime_t max ) {
    const std::vector<prime_t>::const_iterator imin = std::lower_bound( v.begin() , v.end() , min );
    const std::vector<prime_t>::const_iterator imax = std::lower_bound( v.begin() , v.end() , max );
    return imax - imin + (imax != v.end() && *imax == max);
}

int main()
{
    utyp size,max=0;
    std::cin >> size;
    std::vector< utyp > lower(size);
    std::vector< utyp > upper(size);

    for( utyp i=0 ; i<size ; i++ ) {
        std::cin >> lower[i];
        std::cin >> upper[i];
        if( max < upper[i] )
            max = upper[i];
    }

    const std::vector<prime_t> v = genPrime( max );
    for( utyp i=0 ; i<size ; i++ ) {
        std::cout << lower[i] << ' ' << upper[i] << ' ' << countPrimies( v , lower[i] , upper[i] ) << '\n';
    }

    return 0;
}

#endif

Pozdrawiam

1

Wziąłem porządną implementację sita atkina ze strony samych autorów.
Na bazie tej implementajci napisałem program do zadania z tego wątku.
Okazało się, że działa na przykładowych danych aż 20 razy szybciej niż
sito erastotenesa które Ty zaimplementowałeś. Jakbyś swój program
przepisał na typ 64-bitowy, to byśmy mogli porównać wydajność dla
zakresów rzędu 20-30mld. Myślę, że na takich zakresach przyspieszenie
byłoby znacznie większe. Żeby nie było nieporozumień, ten program może
mieć jeszcze jakieś błędy, sprawdźcie sami czy działa poprawnie dla
każdych danych.

Dane na których ja testowałem:

4
3300000000 3500000000
3600000000 3700000000
3800000000 3900000000
4000000000 4100000000

Sito atkina:

time cat data.txt | ./sito_a
9113504
4542381
4530431
4519257

real    0m1.663s
user    0m1.663s
sys     0m0.002s

Sito erastotenesa:

time cat data.txt | ./sito_e
9113504
4542381
4530431
4519257

real    0m32.074s
user    0m31.214s
sys     0m0.869s

Kod programu na bazie sita atkina. Ma nespełna 900 linijek:

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

typedef unsigned long long uint64;
typedef unsigned int uint32;

typedef long long int64;
typedef int int32;


#define PRIMEGEN_WORDS 3600

typedef struct {
  uint32 buf[16][PRIMEGEN_WORDS];
  uint64 p[512]; /* p[num-1] ... p[0], in that order */
  int num;
  int pos; /* next entry to use in buf; WORDS to restart */
  uint64 base;
  uint64 L;
} primegen;

#define B32 PRIMEGEN_WORDS
#define B (PRIMEGEN_WORDS * 32)


static const uint32 two[32] = {
  0x00000001 , 0x00000002 , 0x00000004 , 0x00000008
, 0x00000010 , 0x00000020 , 0x00000040 , 0x00000080
, 0x00000100 , 0x00000200 , 0x00000400 , 0x00000800
, 0x00001000 , 0x00002000 , 0x00004000 , 0x00008000
, 0x00010000 , 0x00020000 , 0x00040000 , 0x00080000
, 0x00100000 , 0x00200000 , 0x00400000 , 0x00800000
, 0x01000000 , 0x02000000 , 0x04000000 , 0x08000000
, 0x10000000 , 0x20000000 , 0x40000000 , 0x80000000
} ;

static void clear(register uint32 (*buf)[B32])
{
  register int i;
  register int j;

  for (j = 0;j < 16;++j) {
    for (i = 0;i < B32;++i)
      (*buf)[i] = ~0;
    ++buf;
  }
}

static void doit4(register uint32 *a,register long x,register long y,int64 start)
{
  long i0;
  long y0;
  register long i;
  register uint32 data;
  register uint32 pos;
  register uint32 bits;

  x += x; x += 15;
  y += 15;

  start += 1000000000;
  while (start < 0) { start += x; x += 30; }
  start -= 1000000000;
  i = start;

  while (i < B) { i += x; x += 30; }

  for (;;) {
    x -= 30;
    if (x <= 15) return;
    i -= x;

    while (i < 0) { i += y; y += 30; }

    i0 = i; y0 = y;
    while (i < B) {
      pos = i; data = i;
      pos >>= 5; data &= 31;
      i += y; y += 30;
      bits = a[pos]; data = two[data];
      bits ^= data;
      a[pos] = bits;
    }
    i = i0; y = y0;
  }
}

static void doit6(register uint32 *a,register long x,register long y,int64 start)
{
  long i0;
  long y0;
  register long i;
  register uint32 data;
  register uint32 pos;
  register uint32 bits;

  x += 5;
  y += 15;

  start += 1000000000;
  while (start < 0) { start += x; x += 10; }
  start -= 1000000000;
  i = start;
  while (i < B) { i += x; x += 10; }

  for (;;) {
    x -= 10;
    if (x <= 5) return;
    i -= x;

    while (i < 0) { i += y; y += 30; }

    i0 = i; y0 = y;
    while (i < B) {
      pos = i; data = i;
      pos >>= 5; data &= 31;
      i += y; y += 30;
      bits = a[pos]; data = two[data];
      bits ^= data;
      a[pos] = bits;
    }
    i = i0; y = y0;
  }
}

static void doit12(register uint32 *a,register long x,register long y,int64 start)
{
  long i0;
  long y0;
  register long i;
  register uint32 data;
  register uint32 pos;
  register uint32 bits;

  x += 5;

  start += 1000000000;
  while (start < 0) { start += x; x += 10; }
  start -= 1000000000;
  i = start;
  while (i < 0) { i += x; x += 10; }

  y += 15;
  x += 10;

  for (;;) {
    while (i >= B) {
      if (x <= y) return;
      i -= y;
      y += 30;
    }
    i0 = i;
    y0 = y;
    while ((i >= 0) && (y < x)) {
      pos = i; data = i;
      pos >>= 5; data &= 31;
      i -= y;
      y += 30;
      bits = a[pos]; data = two[data];
      bits ^= data;
      a[pos] = bits;
    }
    i = i0;
    y = y0;
    i += x - 10;
    x += 10;
  }
}

static const int deltainverse[60] = {
 -1,B32 * 0,-1,-1,-1,-1,-1,B32 * 1,-1,-1,-1,B32 * 2,-1,B32 * 3,-1
,-1,-1,B32 * 4,-1,B32 * 5,-1,-1,-1,B32 * 6,-1,-1,-1,-1,-1,B32 * 7
,-1,B32 * 8,-1,-1,-1,-1,-1,B32 * 9,-1,-1,-1,B32 * 10,-1,B32 * 11,-1
,-1,-1,B32 * 12,-1,B32 * 13,-1,-1,-1,B32 * 14,-1,-1,-1,-1,-1,B32 * 15
} ;

static void squarefree1big(uint32 (*buf)[B32],uint64 base,uint32 q,uint64 qq)
{
  uint64 i;
  uint32 pos;
  int n;
  uint64 bound = base + 60 * B;

  while (qq < bound) {
    if (bound < 2000000000)
      i = qq - (((uint32) base) % ((uint32) qq));
    else
      i = qq - (base % qq);
    if (!(i & 1)) i += qq;

    if (i < B * 60) {
      pos = i;
      n = deltainverse[pos % 60];
      if (n >= 0) {
        pos /= 60;
        (*buf)[n + (pos >> 5)] |= two[pos & 31];
      }
    }

    qq += q; q += 1800;
  }
}

static void squarefree1(register uint32 (*buf)[B32],uint64 L,uint32 q)
{
  uint32 qq;
  register uint32 qqhigh;
  uint32 i;
  register uint32 ilow;
  register uint32 ihigh;
  register int n;
  uint64 base;

  base = 60 * L;
  qq = q * q;
  q = 60 * q + 900;

  while (qq < B * 60) {
    if (base < 2000000000)
      i = qq - (((uint32) base) % qq);
    else
      i = qq - (base % qq);
    if (!(i & 1)) i += qq;

    if (i < B * 60) {
      qqhigh = qq / 60;
      ilow = i % 60; ihigh = i / 60;

      qqhigh += qqhigh;
      while (ihigh < B) {
        n = deltainverse[ilow];
        if (n >= 0)
          (*buf)[n + (ihigh >> 5)] |= two[ihigh & 31];

        ilow += 2; ihigh += qqhigh;
        if (ilow >= 60) { ilow -= 60; ihigh += 1; }
      }
    }

    qq += q; q += 1800;
  }

  squarefree1big(buf,base,q,qq);
}

static void squarefree49big(uint32 (*buf)[B32],uint64 base,uint32 q,uint64 qq)
{
  uint64 i;
  uint32 pos;
  int n;
  uint64 bound = base + 60 * B;

  while (qq < bound) {
    if (bound < 2000000000)
      i = qq - (((uint32) base) % ((uint32) qq));
    else
      i = qq - (base % qq);
    if (!(i & 1)) i += qq;

    if (i < B * 60) {
      pos = i;
      n = deltainverse[pos % 60];
      if (n >= 0) {
        pos /= 60;
        (*buf)[n + (pos >> 5)] |= two[pos & 31];
      }
    }

    qq += q; q += 1800;
  }
}

static void squarefree49(register uint32 (*buf)[B32],uint64 L,uint32 q)
{
  uint32 qq;
  register uint32 qqhigh;
  uint32 i;
  register uint32 ilow;
  register uint32 ihigh;
  register int n;
  uint64 base = 60 * L;

  qq = q * q;
  q = 60 * q + 900;

  while (qq < B * 60) {
    if (base < 2000000000)
      i = qq - (((uint32) base) % qq);
    else
      i = qq - (base % qq);
    if (!(i & 1)) i += qq;

    if (i < B * 60) {
      qqhigh = qq / 60;
      ilow = i % 60; ihigh = i / 60;

      qqhigh += qqhigh;
      qqhigh += 1;
      while (ihigh < B) {
        n = deltainverse[ilow];
        if (n >= 0)
          (*buf)[n + (ihigh >> 5)] |= two[ihigh & 31];

        ilow += 38; ihigh += qqhigh;
        if (ilow >= 60) { ilow -= 60; ihigh += 1; }
      }
    }

    qq += q; q += 1800;
  }

  squarefree49big(buf,base,q,qq);
}

/* squares of primes >= 7, < 240 */
uint32 qqtab[49] = {
  49,121,169,289,361,529,841,961,1369,1681
 ,1849,2209,2809,3481,3721,4489,5041,5329,6241,6889
 ,7921,9409,10201,10609,11449,11881,12769,16129,17161,18769
 ,19321,22201,22801,24649,26569,27889,29929,32041,32761,36481
 ,37249,38809,39601,44521,49729,51529,52441,54289,57121
} ;

/* (qq * 11 + 1) / 60 or (qq * 59 + 1) / 60 */
uint32 qq60tab[49] = {
  9,119,31,53,355,97,827,945,251,1653
 ,339,405,515,3423,3659,823,4957,977,6137
 ,1263,7789,1725,10031,1945,2099,11683,2341,2957
 ,16875,3441,18999,21831,22421,4519,4871,5113,5487
 ,31507,32215,35873,6829,7115,38941,43779,9117,9447,51567,9953,56169
} ;

static void squarefreetiny(register uint32 *a,uint32 *Lmodqq,int d)
{
  int j;
  register uint32 k;
  register uint32 qq;
  register uint32 pos;
  register uint32 data;
  register uint32 bits;

  for (j = 0;j < 49;++j) {
    qq = qqtab[j];
    k = qq - 1 - ((Lmodqq[j] + qq60tab[j] * d - 1) % qq);
    while (k < B) {
      pos = k;
      data = k;
      pos >>= 5;
      data &= 31;
      k += qq;
      bits = a[pos];
      data = two[data];
      bits |= data;
      a[pos] = bits;
    }
  }
}

typedef struct { char index; char f; char g; char k; } todo;

static const todo for4[] = {
  {0,2,15,4} , {0,3,5,1} , {0,3,25,11} , {0,5,9,3}
, {0,5,21,9} , {0,7,15,7} , {0,8,15,8} , {0,10,9,8}
, {0,10,21,14} , {0,12,5,10} , {0,12,25,20} , {0,13,15,15}
, {0,15,1,15} , {0,15,11,17} , {0,15,19,21} , {0,15,29,29}
, {3,1,3,0} , {3,1,27,12} , {3,4,3,1} , {3,4,27,13}
, {3,6,7,3} , {3,6,13,5} , {3,6,17,7} , {3,6,23,11}
, {3,9,7,6} , {3,9,13,8} , {3,9,17,10} , {3,9,23,14}
, {3,11,3,8} , {3,11,27,20} , {3,14,3,13} , {3,14,27,25}
, {4,2,1,0} , {4,2,11,2} , {4,2,19,6} , {4,2,29,14}
, {4,7,1,3} , {4,7,11,5} , {4,7,19,9} , {4,7,29,17}
, {4,8,1,4} , {4,8,11,6} , {4,8,19,10} , {4,8,29,18}
, {4,13,1,11} , {4,13,11,13} , {4,13,19,17} , {4,13,29,25}
, {7,1,5,0} , {7,1,25,10} , {7,4,5,1} , {7,4,25,11}
, {7,5,7,2} , {7,5,13,4} , {7,5,17,6} , {7,5,23,10}
, {7,10,7,7} , {7,10,13,9} , {7,10,17,11} , {7,10,23,15}
, {7,11,5,8} , {7,11,25,18} , {7,14,5,13} , {7,14,25,23}
, {9,2,9,1} , {9,2,21,7} , {9,3,1,0} , {9,3,11,2}
, {9,3,19,6} , {9,3,29,14} , {9,7,9,4} , {9,7,21,10}
, {9,8,9,5} , {9,8,21,11} , {9,12,1,9} , {9,12,11,11}
, {9,12,19,15} , {9,12,29,23} , {9,13,9,12} , {9,13,21,18}
, {10,2,5,0} , {10,2,25,10} , {10,5,1,1} , {10,5,11,3}
, {10,5,19,7} , {10,5,29,15} , {10,7,5,3} , {10,7,25,13}
, {10,8,5,4} , {10,8,25,14} , {10,10,1,6} , {10,10,11,8}
, {10,10,19,12} , {10,10,29,20} , {10,13,5,11} , {10,13,25,21}
, {13,1,15,3} , {13,4,15,4} , {13,5,3,1} , {13,5,27,13}
, {13,6,5,2} , {13,6,25,12} , {13,9,5,5} , {13,9,25,15}
, {13,10,3,6} , {13,10,27,18} , {13,11,15,11} , {13,14,15,16}
, {13,15,7,15} , {13,15,13,17} , {13,15,17,19} , {13,15,23,23}
, {14,1,7,0} , {14,1,13,2} , {14,1,17,4} , {14,1,23,8}
, {14,4,7,1} , {14,4,13,3} , {14,4,17,5} , {14,4,23,9}
, {14,11,7,8} , {14,11,13,10} , {14,11,17,12} , {14,11,23,16}
, {14,14,7,13} , {14,14,13,15} , {14,14,17,17} , {14,14,23,21}
} ;

static const todo for6[] = {
  {1,1,2,0} , {1,1,8,1} , {1,1,22,8} , {1,1,28,13}
, {1,3,10,2} , {1,3,20,7} , {1,7,10,4} , {1,7,20,9}
, {1,9,2,4} , {1,9,8,5} , {1,9,22,12} , {1,9,28,17}
, {5,1,4,0} , {5,1,14,3} , {5,1,16,4} , {5,1,26,11}
, {5,5,2,1} , {5,5,8,2} , {5,5,22,9} , {5,5,28,14}
, {5,9,4,4} , {5,9,14,7} , {5,9,16,8} , {5,9,26,15}
, {8,3,2,0} , {8,3,8,1} , {8,3,22,8} , {8,3,28,13}
, {8,5,4,1} , {8,5,14,4} , {8,5,16,5} , {8,5,26,12}
, {8,7,2,2} , {8,7,8,3} , {8,7,22,10} , {8,7,28,15}
, {11,1,10,1} , {11,1,20,6} , {11,3,4,0} , {11,3,14,3}
, {11,3,16,4} , {11,3,26,11} , {11,7,4,2} , {11,7,14,5}
, {11,7,16,6} , {11,7,26,13} , {11,9,10,5} , {11,9,20,10}
} ;

static const todo for12[] = {
  {2,2,1,0} , {2,2,11,-2} , {2,2,19,-6} , {2,2,29,-14}
, {2,3,4,0} , {2,3,14,-3} , {2,3,16,-4} , {2,3,26,-11}
, {2,5,2,1} , {2,5,8,0} , {2,5,22,-7} , {2,5,28,-12}
, {2,7,4,2} , {2,7,14,-1} , {2,7,16,-2} , {2,7,26,-9}
, {2,8,1,3} , {2,8,11,1} , {2,8,19,-3} , {2,8,29,-11}
, {2,10,7,4} , {2,10,13,2} , {2,10,17,0} , {2,10,23,-4}
, {6,1,10,-2} , {6,1,20,-7} , {6,2,7,-1} , {6,2,13,-3}
, {6,2,17,-5} , {6,2,23,-9} , {6,3,2,0} , {6,3,8,-1}
, {6,3,22,-8} , {6,3,28,-13} , {6,4,5,0} , {6,4,25,-10}
, {6,6,5,1} , {6,6,25,-9} , {6,7,2,2} , {6,7,8,1}
, {6,7,22,-6} , {6,7,28,-11} , {6,8,7,2} , {6,8,13,0}
, {6,8,17,-2} , {6,8,23,-6} , {6,9,10,2} , {6,9,20,-3}
, {12,1,4,-1} , {12,1,14,-4} , {12,1,16,-5} , {12,1,26,-12}
, {12,2,5,-1} , {12,2,25,-11} , {12,3,10,-2} , {12,3,20,-7}
, {12,4,1,0} , {12,4,11,-2} , {12,4,19,-6} , {12,4,29,-14}
, {12,6,1,1} , {12,6,11,-1} , {12,6,19,-5} , {12,6,29,-13}
, {12,7,10,0} , {12,7,20,-5} , {12,8,5,2} , {12,8,25,-8}
, {12,9,4,3} , {12,9,14,0} , {12,9,16,-1} , {12,9,26,-8}
, {15,1,2,-1} , {15,1,8,-2} , {15,1,22,-9} , {15,1,28,-14}
, {15,4,7,-1} , {15,4,13,-3} , {15,4,17,-5} , {15,4,23,-9}
, {15,5,4,0} , {15,5,14,-3} , {15,5,16,-4} , {15,5,26,-11}
, {15,6,7,0} , {15,6,13,-2} , {15,6,17,-4} , {15,6,23,-8}
, {15,9,2,3} , {15,9,8,2} , {15,9,22,-5} , {15,9,28,-10}
, {15,10,1,4} , {15,10,11,2} , {15,10,19,-2} , {15,10,29,-10}
} ;

void primegen_sieve(primegen *pg)
{
  uint32 (*buf)[B32];
  uint64 L;
  int i;
  uint32 Lmodqq[49];

  buf = pg->buf;
  L = pg->L;

  if (L > 2000000000)
    for (i = 0;i < 49;++i)
      Lmodqq[i] = L % qqtab[i];
  else
    for (i = 0;i < 49;++i)
      Lmodqq[i] = ((uint32) L) % qqtab[i];

  clear(buf);

  for (i = 0;i < 16;++i)
    doit4(buf[0],for4[i].f,for4[i].g,(int64) for4[i].k - L);
  squarefreetiny(buf[0],Lmodqq,1);
  for (;i < 32;++i)
    doit4(buf[3],for4[i].f,for4[i].g,(int64) for4[i].k - L);
  squarefreetiny(buf[3],Lmodqq,13);
  for (;i < 48;++i)
    doit4(buf[4],for4[i].f,for4[i].g,(int64) for4[i].k - L);
  squarefreetiny(buf[4],Lmodqq,17);
  for (;i < 64;++i)
    doit4(buf[7],for4[i].f,for4[i].g,(int64) for4[i].k - L);
  squarefreetiny(buf[7],Lmodqq,29);
  for (;i < 80;++i)
    doit4(buf[9],for4[i].f,for4[i].g,(int64) for4[i].k - L);
  squarefreetiny(buf[9],Lmodqq,37);
  for (;i < 96;++i)
    doit4(buf[10],for4[i].f,for4[i].g,(int64) for4[i].k - L);
  squarefreetiny(buf[10],Lmodqq,41);
  for (;i < 112;++i)
    doit4(buf[13],for4[i].f,for4[i].g,(int64) for4[i].k - L);
  squarefreetiny(buf[13],Lmodqq,49);
  for (;i < 128;++i)
    doit4(buf[14],for4[i].f,for4[i].g,(int64) for4[i].k - L);
  squarefreetiny(buf[14],Lmodqq,53);

  for (i = 0;i < 12;++i)
    doit6(buf[1],for6[i].f,for6[i].g,(int64) for6[i].k - L);
  squarefreetiny(buf[1],Lmodqq,7);
  for (;i < 24;++i)
    doit6(buf[5],for6[i].f,for6[i].g,(int64) for6[i].k - L);
  squarefreetiny(buf[5],Lmodqq,19);
  for (;i < 36;++i)
    doit6(buf[8],for6[i].f,for6[i].g,(int64) for6[i].k - L);
  squarefreetiny(buf[8],Lmodqq,31);
  for (;i < 48;++i)
    doit6(buf[11],for6[i].f,for6[i].g,(int64) for6[i].k - L);
  squarefreetiny(buf[11],Lmodqq,43);

  for (i = 0;i < 24;++i)
    doit12(buf[2],for12[i].f,for12[i].g,(int64) for12[i].k - L);
  squarefreetiny(buf[2],Lmodqq,11);
  for (;i < 48;++i)
    doit12(buf[6],for12[i].f,for12[i].g,(int64) for12[i].k - L);
  squarefreetiny(buf[6],Lmodqq,23);
  for (;i < 72;++i)
    doit12(buf[12],for12[i].f,for12[i].g,(int64) for12[i].k - L);
  squarefreetiny(buf[12],Lmodqq,47);
  for (;i < 96;++i)
    doit12(buf[15],for12[i].f,for12[i].g,(int64) for12[i].k - L);
  squarefreetiny(buf[15],Lmodqq,59);

  squarefree49(buf,L,247);
  squarefree49(buf,L,253);
  squarefree49(buf,L,257);
  squarefree49(buf,L,263);
  squarefree1(buf,L,241);
  squarefree1(buf,L,251);
  squarefree1(buf,L,259);
  squarefree1(buf,L,269);
}

unsigned int scan_uint64(char *s,uint64 *u)
{
  unsigned int pos = 0;
  uint64 result = 0;
  uint64 c;
  while ((c = (uint64) (unsigned char) (s[pos] - '0')) < 10) {
    result = result * 10 + c;
    ++pos;
  }
  *u = result;
  return pos;
}

unsigned int fmt_uint64(char *s,uint64 u)
{
  unsigned int len = 1;
  uint64 q = u;
  while (q > 9) { ++len; q /= 10; }
  if (s) { s += len; do { *--s = '0' + (u % 10); u /= 10; } while(u); }
  return len;
}

void primegen_init(primegen *pg)
{
  pg->L = 1;
  pg->base = 60;

  pg->pos = PRIMEGEN_WORDS;

  pg->p[0] = 59;
  pg->p[1] = 53;
  pg->p[2] = 47;
  pg->p[3] = 43;
  pg->p[4] = 41;
  pg->p[5] = 37;
  pg->p[6] = 31;
  pg->p[7] = 29;
  pg->p[8] = 23;
  pg->p[9] = 19;
  pg->p[10] = 17;
  pg->p[11] = 13;
  pg->p[12] = 11;
  pg->p[13] = 7;
  pg->p[14] = 5;
  pg->p[15] = 3;
  pg->p[16] = 2;

  pg->num = 17;
}


void primegen_fill(primegen *pg)
{
  int i;
  uint32 mask;
  uint32 bits0, bits1, bits2, bits3, bits4, bits5, bits6, bits7;
  uint32 bits8, bits9, bits10, bits11, bits12, bits13, bits14, bits15;
  uint64 base;

  i = pg->pos;
  if (i == B32) {
    primegen_sieve(pg);
    pg->L += B;
    i = 0;
  }
  pg->pos = i + 1;

  bits0 = ~pg->buf[0][i];
  bits1 = ~pg->buf[1][i];
  bits2 = ~pg->buf[2][i];
  bits3 = ~pg->buf[3][i];
  bits4 = ~pg->buf[4][i];
  bits5 = ~pg->buf[5][i];
  bits6 = ~pg->buf[6][i];
  bits7 = ~pg->buf[7][i];
  bits8 = ~pg->buf[8][i];
  bits9 = ~pg->buf[9][i];
  bits10 = ~pg->buf[10][i];
  bits11 = ~pg->buf[11][i];
  bits12 = ~pg->buf[12][i];
  bits13 = ~pg->buf[13][i];
  bits14 = ~pg->buf[14][i];
  bits15 = ~pg->buf[15][i];

  base = pg->base + 1920;
  pg->base = base;

  pg->num = 0;

  for (mask = 0x80000000;mask;mask >>= 1) {
    base -= 60;
    if (bits15 & mask) pg->p[pg->num++] = base + 59;
    if (bits14 & mask) pg->p[pg->num++] = base + 53;
    if (bits13 & mask) pg->p[pg->num++] = base + 49;
    if (bits12 & mask) pg->p[pg->num++] = base + 47;
    if (bits11 & mask) pg->p[pg->num++] = base + 43;
    if (bits10 & mask) pg->p[pg->num++] = base + 41;
    if (bits9 & mask) pg->p[pg->num++] = base + 37;
    if (bits8 & mask) pg->p[pg->num++] = base + 31;
    if (bits7 & mask) pg->p[pg->num++] = base + 29;
    if (bits6 & mask) pg->p[pg->num++] = base + 23;
    if (bits5 & mask) pg->p[pg->num++] = base + 19;
    if (bits4 & mask) pg->p[pg->num++] = base + 17;
    if (bits3 & mask) pg->p[pg->num++] = base + 13;
    if (bits2 & mask) pg->p[pg->num++] = base + 11;
    if (bits1 & mask) pg->p[pg->num++] = base + 7;
    if (bits0 & mask) pg->p[pg->num++] = base + 1;
  }
}

uint64 primegen_next(primegen *pg)
{
  while (!pg->num)
    primegen_fill(pg);

  return pg->p[--pg->num];
}

uint64 primegen_peek(primegen *pg)
{
  while (!pg->num)
    primegen_fill(pg);

  return pg->p[pg->num - 1];
}


static const unsigned long pop[256] = {
 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5
,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6
,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6
,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7
,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6
,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7
,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7
,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};

uint64 primegen_count(primegen *pg,uint64 to)
{
  uint64 count = 0;
  register int pos;
  register int j;
  register uint32 bits;
  register uint32 smallcount;

  for (;;) {
    while (pg->num) {
      if (pg->p[pg->num - 1] >= to) return count;
      ++count;
      --pg->num;
    }

    smallcount = 0;
    pos = pg->pos;
    while ((pos < B32) && (pg->base + 1920 < to)) {
      for (j = 0;j < 16;++j) {
    bits = ~pg->buf[j][pos];
    smallcount += pop[bits & 255]; bits >>= 8;
    smallcount += pop[bits & 255]; bits >>= 8;
    smallcount += pop[bits & 255]; bits >>= 8;
    smallcount += pop[bits & 255];
      }
      pg->base += 1920;
      ++pos;
    }
    pg->pos = pos;
    count += smallcount;

    if (pos == B32)
      while (pg->base + B * 60 < to) {
        primegen_sieve(pg);
        pg->L += B;

    smallcount = 0;
        for (j = 0;j < 16;++j)
      for (pos = 0;pos < B32;++pos) {
        bits = ~pg->buf[j][pos];
        smallcount += pop[bits & 255]; bits >>= 8;
        smallcount += pop[bits & 255]; bits >>= 8;
        smallcount += pop[bits & 255]; bits >>= 8;
        smallcount += pop[bits & 255];
      }
        count += smallcount;
        pg->base += B * 60;
      }

    primegen_fill(pg);
  }
}

void primegen_skipto(primegen *pg,uint64 to)
{
  int pos;

  for (;;) {
    while (pg->num) {
      if (pg->p[pg->num - 1] >= to) return;
      --pg->num;
    }

    pos = pg->pos;
    while ((pos < B32) && (pg->base + 1920 < to)) {
      pg->base += 1920;
      ++pos;
    }
    pg->pos = pos;
    if (pos == B32)
      while (pg->base + B * 60 < to) {
        pg->L += B;
        pg->base += B * 60;
      }

    primegen_fill(pg);
  }
}


uint32 mod10[200] = {
 0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
,0,1,2,3,4,5,6,7,8,9 ,0,1,2,3,4,5,6,7,8,9
} ;

uint32 div10[200] = {
 0,0,0,0,0,0,0,0,0,0 ,1,1,1,1,1,1,1,1,1,1
,2,2,2,2,2,2,2,2,2,2 ,3,3,3,3,3,3,3,3,3,3
,4,4,4,4,4,4,4,4,4,4 ,5,5,5,5,5,5,5,5,5,5
,6,6,6,6,6,6,6,6,6,6 ,7,7,7,7,7,7,7,7,7,7
,8,8,8,8,8,8,8,8,8,8 ,9,9,9,9,9,9,9,9,9,9
,10,10,10,10,10,10,10,10,10,10 ,11,11,11,11,11,11,11,11,11,11
,12,12,12,12,12,12,12,12,12,12 ,13,13,13,13,13,13,13,13,13,13
,14,14,14,14,14,14,14,14,14,14 ,15,15,15,15,15,15,15,15,15,15
,16,16,16,16,16,16,16,16,16,16 ,17,17,17,17,17,17,17,17,17,17
,18,18,18,18,18,18,18,18,18,18 ,19,19,19,19,19,19,19,19,19,19
} ;


struct RF {
  uint64 min;
  uint64 max;
};


int fcmp( const void *a , const void *b ) {
    uint64 _a = *((uint64*)a);
    uint64 _b = *((uint64*)b);
    if( _a == _b )
        abort();
    if( _a > _b )
        return +1;
    return -1;
}

int main(int argc,char **argv)
{
  uint64 low = 2;
  uint64 high = 1000000000;

  static primegen pg;


  uint64 p;
  uint32 u;
  uint32 i,j;

  uint32 c_ranges;
  std::vector<RF>     rfs1;
  std::set<uint64>    sdif;

  std::cin >> c_ranges;
  if( c_ranges < 1 )
      abort();
  for( i=0 ; i<c_ranges ; i++ ) {
      RF tmp;
      std::cin >> tmp.min >> tmp.max;
      rfs1.push_back( tmp );
      if( sdif.count(tmp.min) == 0 ) sdif.insert(tmp.min);
      if( sdif.count(tmp.max) == 0 ) sdif.insert(tmp.max);
  }
  std::vector<uint64> vdif;
  std::copy( sdif.begin() , sdif.end() , std::back_inserter(vdif) );
  std::sort( vdif.begin() , vdif.end() );
  vdif.push_back( vdif.back() );
  std::vector<uint64> freq(vdif.size(),0);

  low  = vdif.front();
  high = vdif.back();

  primegen_init(&pg);
  primegen_skipto(&pg,low);
  p = primegen_peek(&pg);

  std::set<uint64> spec;

  for (i=0;;) {
    u = primegen_next(&pg) - p;
    p += u;
    if( p > high )
        break;

    while( p > vdif[i+1] )
        i++;
    if( p < vdif[i+1] ) {
        freq[i] ++ ;
    } else if( p == vdif[i+1] ) {
        spec.insert(p);
    }

//   printf("%lld\n",p);


  }

//  std::cout<<"\n------------------------\n";

//    for( i=0 ; i<vdif.size() ; i++ ) {
//        std::cout << vdif[i] << ' ' << freq[i] << '\n';
//    }

//  std::cout<<"\n------------------------\n";

  for( i=0 ; i<c_ranges ; i++ ) {
    uint64 f = spec.count( rfs1[i].max );
    for( j=0 ; j<vdif.size()-1 ; j++ ) {
        if( vdif[j] >= rfs1[i].min  && vdif[j+1] <= rfs1[i].max ) {
            f += freq[j] + spec.count( vdif[j] );
        }
    }
    std::cout /* << rfs1[i].min << ' ' << rfs1[i].max << ' ' */ << f << '\n';
  }

  return 0;
}

Pozdrawiam

0

Dobra dziękuję wszystkim za pomoc, temat uważam za zamknięty. Dzięki wam dowiedziałem się wielu nowych rzeczy dotyczących programowania :)

0

Tak z ciekawości muszę jeszcze zapytać, czy próbowałeś skompilować i uruchomić ostatnią wersję, tę najdłuższą?
Jeśli tak, to jak u Ciebie działa, nie wywala się? Czy porównywałeś czasy z sitem erastotenesa? Czy ktoś przerobił
sito erastotenesa na typ 64bitowy i uruchomił oba programy na przedziałach rzędu 20-40mld, albo jeszcze większych?
Jeśli tak, to jakie były różnice w czasie?

Pozdrawiam

0

Tak w ogóle to szacun dla kodu ;) Długo nad nim siedziałeś kolego? Pozdrawiam -

Dziękuję :)
Kompiluje się chociaż? :)

Posłużyłem się biblioteką. Prawdziwy szacun należy się twórcy teorii :)

Trochę czasu zajęło mi wyjęcie plików biblioteki do jednego pliku aby dało się ładnie
zaprezentować na forum. Reszta poszła szybko.

Zastanawiałem się jeszcze nad tym kodem i można go jeszcze ulepszyć dla niektórych
danych. Można go łatwo przerobić tak, aby wykorzystywał wszystkie
rdzenie w procesorze. Po małych przeróbkach, możnaby go też uruchomić na wielu
komputerach równocześnie.

Pozdrawiam

1 użytkowników online, w tym zalogowanych: 0, gości: 1