Ещё раз о простых числах...

Раз уж речь сегодня снова зашла об этом, уточню, что в распределении простых чисел никакого секрета нет - при границе поиска n=1022 как раз и выйдет примерно 1,97% простых чисел, раз для числа от 1 до n шанс оказаться простым примерно равен 1/ln(n).

Если взять хоть вот этот файл (архив большой, ~1.5 Мб!) и тупо посчитать, сколько чисел попадает в интервалы одинакового размера, взятые, скажем, с шагом 100000, получим вот что:

распределение простых чисел

Красный пунктир - вышеприведённая формула 1/ln(n).

Программа подсчёта на консольном Си:

#include <stdio.h>
#include <stdlib.h>

void wait() {
 printf ("\nPress ENTER to continue..."); fflush (stdin); getchar();
}

void main() {
 FILE *fp=fopen ("simple.txt","rt");
 if (fp==NULL) {
  printf ("\nCan't open simple.txt"); wait(); exit(1);
 }
 FILE *fw=fopen ("simple_d.txt","wt");
 if (fp==NULL) {
  printf ("\nCan't open simple_d.txt"); wait(); exit(1);
 }
 long int step=100000,i,a,k,n=1;
 for (i=step,k=0;;) {
  fscanf (fp,"%ld",&a);
  if (feof(fp)) break;
  if (a<=i) k++;
  else {
   fprintf (fw,"\n%ld\t%ld",n,k);
   printf ("\n%ld\t%ld",n++,k);
   k=1;
   i+=step;
  }
 }
 fprintf (fw,"\n%ld\t%ld",n,k);
 printf ("\n%ld\t%ld",n,k);
 fclose (fw);
 fclose (fp);
 wait();
}

Можно, конечно, показать распределение по логарфимической шкале с основанием 10 на оси x, приняв начальное step=1 и добавив после k=1; в теле цикла действие step*=10; - но всё это ничего не даст, как и натуральные логарифмы вместо десятичных.

Результаты приведённых бессмысленных расчётов - в приложенном файле, на четвёртом его листе - красивая теоретическая кривая :) Вот по оси y я б ещё подумал, не логарифмировать ли чего где :)

 Распределение простых чисел, документ Excel в архиве ZIP (32 Кб)

Ну а вычёркивания, естественно, можно сделать куда эффективней, хотя бы заметив, что, кроме чисел 2 и 5, все простые числа обязаны заканчиваться на 1, 3, 7 или 9 :)

28.11.2012, 22:31 [9607 просмотров]