Поиск простых чисел

[SerjeyMinsk]

Вот что-то не то у меня

[Someone]

Вот программа на C.

#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define TEST(f,x)   (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define SET(f,x)   *(f+(x)/16)|=1<<(((x)%16L)/2)

int
main(int argc, char *argv[])
{
  unsigned char *feld=NULL, *zzz;
  unsigned long teste=1, max, mom, hits=1, count, alloc, s=0, e=1;
  time_t begin;

  if (argc > 1)
    max = atol (argv[1]) + 10000;
  else
    max = 14010000L;

  while (feld==NULL)
        zzz = feld = malloc (alloc=(((max-=10000L)>>4)+1L));

  for (count=0; count<alloc; count++) *zzz++ = 0x00;

  printf ("Searching prime numbers to : %ld\n", max);

  begin = time (NULL);
  while ((teste+=2) < max)
        if (!TEST(feld, teste)) {
                if  (++hits%2000L==0) {printf (" %ld. prime number\x0d", hits); fflush(stdout);}
                for (mom=3L*teste; mom<max; mom+=teste<<1) SET (feld, mom);
                }

  printf (" %ld prime numbers foundn %ld secs.\n\nShow prime numbers", 
          hits, time(NULL)-begin);

  while (s<e) {
        printf ("\n\nStart of Area : "); fflush (stdout); scanf ("%ld", &s);
        printf ("End   of Area : ");     fflush (stdout); scanf ("%ld", &e);

        count=s-2; if (s%2==0) count++;
        while ((count+=2)<e) if (!TEST(feld,count)) printf ("%ld\t", count);
        }
  free (feld);
  return 0;
}

Вот прогон до миллиарда.

Microsoft Windows XP [Версия 5.1.2600]
(С) Корпорация Майкрософт, 1985-2001.

C:\Documents and Settings\Someone>d:\Programming\CBuilder5\Projects\sieve_c\siev
e_c.exe 1000000000
Searching prime numbers to : 1000000000
 50847534 prime numbers foundn 26 secs.

Show prime numbers

Start of Area : 999999000
End   of Area : 1000000000
999999001       999999017       999999029       999999043       999999059
999999067       999999103       999999107       999999113       999999131
999999137       999999151       999999163       999999181       999999191
999999193       999999197       999999223       999999229       999999323
999999337       999999353       999999391       999999433       999999487
999999491       999999503       999999527       999999541       999999587
999999599       999999607       999999613       999999667       999999677
999999733       999999739       999999751       999999757       999999761
999999797       999999883       999999893       999999929       999999937


Start of Area : End   of Area : ^C
C:\Documents and Settings\Someone>

Вот прогон до 14000000.

C:\Documents and Settings\Someone>d:\Programming\CBuilder5\Projects\sieve_c\siev
e_c.exe
Searching prime numbers to : 14000000
 910077 prime numbers foundn 1 secs.

Show prime numbers

Start of Area : 13999000
End   of Area : 14000000
13999003        13999009        13999057        13999079        13999099
13999121        13999133        13999147        13999159        13999169
13999171        13999189        13999213        13999253        13999267
13999273        13999289        13999291        13999301        13999309
13999351        13999369        13999393        13999397        13999399
13999421        13999423        13999441        13999459        13999463
13999471        13999477        13999481        13999519        13999529
13999537        13999549        13999597        13999603        13999621
13999651        13999673        13999691        13999703        13999723
13999729        13999747        13999757        13999759        13999781
13999787        13999813        13999831        13999871        13999873
13999877        13999889        13999919        13999957        13999961
13999969        13999981

[SerjeyMinsk]

http://ifolder.ru/13778798 Вот видео (20 мб) от квадрата 11111
Видео очень тормознутое получается. Возможно из-за оперативки.
В реальности все за секунду происходит.

[Бодигрим]

SerjeyMinsk в сообщении #239283 писал(а):

Вот что-то не то у меня

Меня терзают смутные подозрения, что вы не скопировали последний символ программы - точку: 54-я строка выглядит как "end."

[SerjeyMinsk]

Бодигрим в сообщении #239289 писал(а):

SerjeyMinsk в сообщении #239283 писал(а):

Вот что-то не то у меня

Меня терзают смутные подозрения, что вы не скопировали последний символ программы - точку: 54-я строка выглядит как "end."

Именно это и было причиной. Извиняюсь.

Number of primes up to 100000 - 9592 time spent: 0.000 secs
Number of primes up to 1000000 - 78498 time spent: 0.031 secs
Number of primes up to 10000000 - 664579 time spent: 0.906 secs
Number of primes up to 100000000 - 5761455 time spent: 10.532 secs

Исходя из визуальных данных пока вроде assa быстрей.
Спасибо. Как бы еще разобраться вставить таймер и туда.
Но уже спать.

[venco]

SerjeyMinsk в сообщении #239293 писал(а):

Исходя из визуальных данных пока вроде assa быстрей.

Не забывайте, что пограмма, что мы вам дали, считает все простые числа до $N^2$, а не в интервале длины $4 N$, как у вас. Решето Эратосфена можно модифицировать, чтобы тоже искать простые числа в диапазоне, и результат получится гораздо быстрее.
К примеру, на моём компьютере та же программа считает все простые числа до $11111^2$ за 7.2 секунды, а в диапазоне от $11109^2$ до $11111^2$ - за одну миллисекунду.
К тому же, код, что вам дали, я специально написал примитивно, безо всяких оптимизаций. Для сравнения, оптимизированный код считает все простые числа до $11111^2$ за 66 миллисекунд.

[SerjeyMinsk]

venco в сообщении #239301 писал(а):

SerjeyMinsk в сообщении #239293 писал(а):

Исходя из визуальных данных пока вроде assa быстрей.

Не забывайте, что пограмма, что мы вам дали, считает все простые числа до $N^2$, а не в интервале длины $4 N$, как у вас. Решето Эратосфена можно модифицировать, чтобы тоже искать простые числа в диапазоне, и результат получится гораздо быстрее.
К примеру, на моём компьютере та же программа считает все простые числа до $11111^2$ за 7.2 секунды, а в диапазоне от $11109^2$ до $11111^2$ - за одну миллисекунду.
К тому же, код, что вам дали, я специально написал примитивно, безо всяких оптимизаций. Для сравнения, оптимизированный код считает все простые числа до $11111^2$ за 66 миллисекунд.

Да, согласен. Я тоже это учитываю и пока рано говорить о том, что все работает быстрее действительно.

[SerjeyMinsk]

Сообщение удалил.

[Бодигрим]

Короче говоря, ваш алгоритм выполняет $O(n)$ (читай: порядка $n$) проходов высеивания при нахождении простых чисел между $n^2$ и $(n-2)^2$. Грамотно организованное решето Эратосфена выполняет лишь $O(n/\ln n)$ проходов высеивания и более универсально, поскольку позволяет высеять все составные числа, не превосходящие $n^2$.

[venco]

Бодигрим в сообщении #239515 писал(а):

Короче говоря, ваш алгоритм выполняет $O(n)$ (читай: порядка $n$) проходов высеивания при нахождении простых чисел между $n^2$ и $(n-2)^2$. Грамотно организованное решето Эратосфена выполняет лишь $O(n/\ln n)$ проходов высеивания и более универсально, поскольку позволяет высеять все составные числа, не превосходящие $n^2$.

Действительно, если оптимизировать внутренний цикл (а без оптимизации сложность - $O(n^2)$), то получится почти решето Эратосфена, только вычёркиваются делители всех нечётных чисел, а не только простых. В результате скорость остаётся хуже решета Эратосфена.
К примеру на моём компьютере после оптимизации
Диапазон $[9999999^2, 10000001^2]$, найдено $1242053$ простых чисел:
SerjeyMinsk: 4.3 сек
Эратосфен: 2.8 сек
Диапазон $[49999999^2, 50000001^2]$, найдено $5641460$ простых чисел:
SerjeyMinsk: 26 сек
Эратосфен: 15 сек

[SerjeyMinsk]

Ребята, да пофиг скорости. Сам факт.
Скиньте, если можете готовую порграмму чтобы с большими числами работала. Сделаю факторизацию еше.

[gris]

SerjeyMinsk писал(а):

writeln('Vvedite ne4etnoe 4islo');
writeln('Prosil zhe ne4etnoe!');
writeln('Budet ',n+1);

Да Вам надо пользовательские интерфейсы писать! Дались Вам эти решёта. По бабкам то же самое, но жить спокойнее.

[SerjeyMinsk]

Ну, а вобще, как думаете. Место есть ему в теории чисел? В википедию там какую?
Метода нет такого нигде или есть?

[gris]

Я без всякой иронии. В тестовом варианте такое внимание к юзеру - это достойно уважения.

Но вопрос остался открытым. Маленькие числа никому не нужны. Ваш алгоритм работает правильно и это главное. Надо сравнивать скорости для тысячезначных чисел. Вот тогда и будет видно - что эффектиивнее. Я сомневаюсь, что решёта реализованы для таких чисел.

[Xaositect]

gris в сообщении #239545 писал(а):

Но вопрос остался открытым. Маленькие числа никому не нужны. Ваш алгоритм работает правильно и это главное. Надо сравнивать скорости для тысячезначных чисел. Вот тогда и будет видно - что эффектиивнее. Я сомневаюсь, что решёта реализованы для таких чисел.

Тут вот асимптотическую оценку привели, из которой следует, что дальше будет только хуже.
Вообще, если я не ошибаюсь, этот метод - всего лишь небольшая оптимизация очень простого решета, которое проверяет делимость на 2 и на все нечетные числа.
Если нужно, вечером напишу подробнее.