close

Вход

Забыли?

вход по аккаунту

?

Лабораторная работа (2)

код для вставкиСкачать
Лабораторная работа №1
Нахождение простых чисел с помощью решета Эратосфена
Требуется составить программу по нахождению всех простых чисел с помощью алгоритма Эратосфена, которые меньше заданного числа N. Написать их по 10 чисел в строке. Вывести количество полученных простых чисел и провести оценку по формуле Адамара.
Реализация алгоритма:
long int N, *a; printf("Input number ");
scanf("%d", &N);
a=(long int*)calloc(N, sizeof(long int));
for (long int i=1; i<=N; i++) {
a[i]=i;
}
long int j=2, tmp=0;
int K=1;
while (K<sqrt(N))
{ tmp=a[j];
for (long int i=j+1; i<=N; i++)
if (a[i]&&(a[i]%tmp==0)) a[i]=0;
j++;
while ((j<=N)&&!a[j])
j++;
K++;
}
Цикл продолжается до , так как все составные числа, стоящие за будут уже вычеркнуты. Числа состоят из двух множителей, большего и меньшего - поэтому составные числа после будут вычеркнуты при проходе по меньшему множителю.
Кроме того было расчитано значение по закону Адамара. При N = 100 реальное = 25, а рассчитанное по закону Адамара = 21,71. Таким образом при N = 100 погрешность составляет . При N = 1000000 реальное = 78498, а рассчитанное по закону Адамара = 72382,41. Таким образом при N = 100 погрешность составляет . Соответственно при увеличении N увеличивается точность расчета количества простых чисел по закону Адамара.
Документ
Категория
Рефераты
Просмотров
34
Размер файла
22 Кб
Теги
работа, лабораторная
1/--страниц
Пожаловаться на содержимое документа