Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > длинные простые числа

Автор: 0x00000000 6.2.2009, 01:21

Помогите добавить в эту програмку вывод не всех простых чисел а только каждое 10000000 число   тоесть n1 = 10000000 по счету n2 = 20000000  ..... n45 = 450000000 прошли еще 10милионов простых и вывели второе и так до 450 милионов тоесть 45 простых чисел(( Код #include <stdio.h> #include <math.h> #include <conio.h> #define true 1 #define false 0 int isPrime (int n) {               int is_prime = true;     int i = 2;     double sqrt_n = sqrt((double) n);     while (i <= sqrt_n) {                     if (n % i == 0) {                                       is_prime = false;             break;                        }           i++;                                                        }           return is_prime; } int main() { int i;   int k=1;   for ( i = 2; i <= 10000000000; ++i)   {       if (isPrime(i))                           printf ("element %d - %d\n",k++,i);   }   getch();           return 0; }

Автор: mes 6.2.2009, 02:11

замени : Код       int k=1;       ...       if (isPrime(i))                           printf ("element %d - %d\n",k++,i); на Код       int k=0;       ...       if (isPrime(i))                  if ((++k % 1000000)==0)                              printf ("element %d - %d\n",k,i); исправлено

Автор: math64 6.2.2009, 09:22

Работа программы ускорится, если проверять деление не на все числа от 2 до sqrt(n), а только на уже найденные простые числа в этом интервале (решето Эратосфена)

Автор: bsa 6.2.2009, 11:25

Цитата(math64 @ 6.2.2009,  09:22) Работа программы ускорится, если проверять деление не на все числа от 2 до sqrt(n), а только на уже найденные простые числа в этом интервале (решето Эратосфена) Очень много памяти жрать это будет... Для начала, можно просто исключить четные числа большие 2-х

Автор: Dov 6.2.2009, 16:23

Цитата(0x00000000 @  6.2.2009,  00:21 ) for ( i = 2; i <= 10000000000; ++i) выход за пределы диапазона для типа int . Цитата(mes @  6.2.2009,  01:11 ) if (++k ==1000000)  mes, может ты так хотел сказать:  Код if ((++k % 10000000) == 0)

Автор: mes 7.2.2009, 00:39

Цитата(Dov @  6.2.2009,  15:23 ) mes, может ты так хотел сказать:  спасибо за исправление, каюсь .. напортачил

Автор: 0x00000000 9.2.2009, 17:31

вот поиск через другой алгоритм только что тут что там нехватает обычныйх типов инт и лонг инт(((( что можно сделать? Код #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <math.h> #include <time.h> #include <dos.h> #define limit 18000000000 //#define N 500000000 const unsigned long int N=500000000; //long int limit = 180000000; long int sqr_lim; bool is_prime[N]; long int x2=0, y2; long int i, j; long int n, k; int main (){ //FILE *fp; //fp=fopen("prime.txt", "w"); clock_t start, end; start = clock(); // Инициализация решета sqr_lim = (int)sqrt((long double)limit); for (i = 0; i <= limit; i++) is_prime[i] = false; is_prime[2] = true; is_prime[3] = true; // Предположительно простые - это целые с нечетным числом // представлений в данных квадратных формах. // x2 и y2 - это квадраты i и j (оптимизация). x2 = 0; for (i = 1; i <= sqr_lim; i++) {     x2 += 2 * i - 1;     y2 = 0;     for (j = 1; j <= sqr_lim; j++) {         y2 += 2 * j - 1;         n = 4 * x2 + y2;         if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))             is_prime[n] = !is_prime[n];         n = 3 * x2 + y2;         n -= x2; // Оптимизация         if ((n <= limit) && (n % 12 == 7))             is_prime[n] = !is_prime[n];         n = 3 * x2 - y2;         n -= 2 * y2; // Оптимизация         if ((i > j) && (n <= limit) && (n % 12 == 11))             is_prime[n] = !is_prime[n];     } } // Отсеиваем квадраты простых чисел в интервале [5, sqrt(limit)]. // (основной этап не может их отсеять) for (i = 5; i <= sqr_lim; i++) {     if (is_prime[i]) {         n = i * i;         for (j = n; j <= limit; j += n) {             is_prime[j] = false;         }     } } // Вывод списка простых чисел в консоль. for (int i = 2; i <= limit; i++) {     if (is_prime[i]) {     if ((++k % 1000000)==0)                 {                 printf ("prime %d - %d\n", k,i);                 //fprintf (fp, "prime %d - %d\n",k,i);                 }        //printf(", %d", i);     }     }     end = clock();     printf("The time was: %f\n", (end - start) / CLK_TCK);     getch();     //fclose(fp);     return 0; }

Автор: bsa 9.2.2009, 18:46

1. делать свой тип (например, int512_t) 2. делать через массив десятичных знаков (очень долго работать будет). Может ты задание не так понял? Потому что то, что ты хочешь является вполне конкретной научной задачей, для которой используют распределенные вычисления и супер-компьютеры.

Автор: Ln78 10.2.2009, 09:58

Цитата(math64 @  6.2.2009,  09:22 ) Работа программы ускорится, если проверять деление не на все числа от 2 до sqrt(n), а только на уже найденные простые числа в этом интервале (решето Эратосфена)  Цитата(bsa @  6.2.2009,  11:25 ) Очень много памяти жрать это будет... Для начала, можно просто исключить четные числа большие 2-х    Памяти не так много, но и даже с этой модификацией программа будет работать ОЧЕНЬ долго. А уж если проверять вообще все, то НЕРЕАЛЬНО долго. По сути, нам нужно найти 450 миллионов простых чисел. Оценка сверху (по формуле Чебышёва) даёт, что проверить надо порядка 11 миллиардов чисел (10 миллиардов не хватит). Проверяем до квадратного корня, т.е. примерно до 105 тысяч. А простых чисел, меньших 105000 примерно 9100, т.е. памяти потребуется не так много, порядка 10 тысяч 32-разрядных целых чисел. Использовать, вероятно, лучше всего 64-разрядные целые числа. Очевидно, что в цикле, если начать с 3, идти нужно с шагом 2. Может ещё можно подумать, как убыстрить расчёт. P.S. Забавно, что самым сложным для топикстартера в этой задаче показалось добавить условие на печать

Автор: Ln78 10.2.2009, 10:56

Вот такой вариант, наверное, не самый оптимальный. Для простоты я всё поместил в одну функцию, в том числе и выходной массив nOutPrime. Проверял при NSelectedForUse = 100000, вроде правильно работает. Код void FindPrime( ) {    const unsigned int NP = 45;    unsigned long long nOutPrime[NP] = {0};    unsigned int npout = 0;    unsigned int nCountPrime = 1;    unsigned int NSelectedForUse = 10000000;    unsigned long long nLimit = 11000000000;     const int Npp = 10000;    unsigned int nTestPrime[Npp] = {2};    unsigned int npp = 1;    unsigned int nNmax = 3;    unsigned long long i = 3;    unsigned int k;    bool bPrime;    unsigned int nMaxInd = 1;    unsigned long long nMaxNumber = 4;    for( i = 3; i < nLimit; i+=2 )    {       if( i > nMaxNumber )       {          nMaxNumber = nTestPrime[ nMaxInd ] * nTestPrime[ nMaxInd ];          nMaxInd++;       }       bPrime = true;       for( k = 0; k < nMaxInd; k++ )       {          if( i % nTestPrime[k] == 0 )          {             bPrime = false;             break;          }       }       if( bPrime )       {          if( npp < Npp )          {             nTestPrime[ npp++ ] = i;          }          if( ++nCountPrime % NSelectedForUse == 0 )          {             nOutPrime[ npout++ ] = i;             if( npout >= NP )                break;          }       }    } }

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)