VPF::длинные простые числа - Форум программистов

0x00000000

Дата 6.2.2009, 01:21 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 27.8.2008

Репутация: нет
Всего: -1

Помогите добавить в эту програмку вывод не всех простых чисел а только каждое 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 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

замени :

Код


      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);

исправлено

Это сообщение отредактировал(а) mes - 7.2.2009, 00:38

--------------------

http://opendots.net

math64

Дата 6.2.2009, 09:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72

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

bsa

Дата 6.2.2009, 11:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Цитата(math64 @ 6.2.2009, 09:22)

Очень много памяти жрать это будет...
Для начала, можно просто исключить четные числа большие 2-х smile

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Dov

Дата 6.2.2009, 16:23 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 11
Всего: 88

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(Dov @ 6.2.2009, 15:23

)

mes, может ты так хотел сказать:

спасибо за исправление, каюсь .. напортачил smile

--------------------

http://opendots.net

0x00000000

Дата 9.2.2009, 17:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 27.8.2008

Репутация: нет
Всего: -1

вот поиск через другой алгоритм только что тут что там нехватает обычныйх типов инт и лонг инт((((
что можно сделать?

Код


#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;
}

Это сообщение отредактировал(а) 0x00000000 - 12.2.2009, 00:38

bsa

Дата 9.2.2009, 18:46 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

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

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Ln78

Дата 10.2.2009, 09:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 274
Регистрация: 25.11.2006

Репутация: нет
Всего: 15

Цитата(math64 @ 6.2.2009, 09:22

)

Цитата(bsa @ 6.2.2009, 11:25

)

Очень много памяти жрать это будет...
Для начала, можно просто исключить четные числа большие 2-х

Памяти не так много, но и даже с этой модификацией программа будет работать ОЧЕНЬ долго. А уж если проверять вообще все, то НЕРЕАЛЬНО долго.
По сути, нам нужно найти 450 миллионов простых чисел. Оценка сверху (по формуле Чебышёва) даёт, что проверить надо порядка 11 миллиардов чисел (10 миллиардов не хватит). Проверяем до квадратного корня, т.е. примерно до 105 тысяч. А простых чисел, меньших 105000 примерно 9100, т.е. памяти потребуется не так много, порядка 10 тысяч 32-разрядных целых чисел. Использовать, вероятно, лучше всего 64-разрядные целые числа. Очевидно, что в цикле, если начать с 3, идти нужно с шагом 2. Может ещё можно подумать, как убыстрить расчёт.

P.S. Забавно, что самым сложным для топикстартера в этой задаче показалось добавить условие на печать smile

Ln78

Дата 10.2.2009, 10:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 274
Регистрация: 25.11.2006

Репутация: нет
Всего: 15

Вот такой вариант, наверное, не самый оптимальный. Для простоты я всё поместил в одну функцию, в том числе и выходной массив 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;
         }
      }
   }

}

Это сообщение отредактировал(а) Ln78 - 10.2.2009, 10:56

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »