«Основы теории чисел»



страница6/7
Дата21.10.2016
Размер0,8 Mb.
1   2   3   4   5   6   7

1.3. Бинарный алгоритм Евклида.

Вычислить НОД(a,b) при помощи бинарного алгоритма Евклида, где:

а) a = 665, b = 163;

б) a = 153, b = 765;

в) a = 814, b = 661;

г) a = 508, b = 274;

д) a = 210, b = 836.

Вычислить НОД(a,b) при помощи бинарного алгоритма Евклида, где:

а) a = 665, b = 163.

Решение:

665=20∙665, k1=0; 163=20∙163, k2=0.

=> k=min(k1,k2)=0, a1=max(665,163)=665, b1=min(665,163)=163.

c=665-163=502=21∙251, c1=251, a1=max(b1,c1)=251, b1=min(b1,c1)=163.

c=251-163=88=23∙11, c1=11, a1=163, b1=11.

c=163-11=152=23∙19, c1=19, a1=19, b1=11.

c=19-11=8=23∙1, c1=1, a1=11, b1=1.

c=11-1=10=21∙5, c1=5, a1=5, b1=1.

c=5-1=4=22∙1, c1=1, a1=1, b1=1.

Ответ: НОД(665,163)=2k∙b1=20∙1=1.

б) a = 153, b = 765.

Решение:

153=20∙153, k1=0; 765=20∙765, k2=0.

=> k=min(k1,k2)=0, a1=max(765,153)=765, b1=min(765,153)=153.

c=765-153=612=22∙153, c1=153, a1=max(b1,c1)=153, b1=min(b1,c1)=153.

Ответ: НОД(153,765)=2k∙b1=20∙153=153.

в) a = 814, b = 661.

Решение:

814=21∙407, k1=1; 661=20∙661, k2=0.

=> k=min(k1,k2)=0, a1=max(661,407)=661, b1=min(661,407)=407.

c=661-407=254=21∙127, c1=127, a1=max(b1,c1)=407, b1=min(b1,c1)=127.

c=407-127=280=23∙35, c1=35, a1=127, b1=35.

c=127-35=92=22∙23, c1=23, a1=35, b1=23.

c=35-23=12=22∙3, c1=3, a1=23, b1=3.

c=23-3=20=22∙5, c1=5, a1=5, b1=3.

c=5-3=2=21∙1, c1=1, a1=3, b1=1.

c=3-1=2=21∙1, c1=1, a1=1, b1=1.

Ответ: НОД(814,661)=2k∙b1=20∙1=1.

г) a = 508, b = 274.

Решение:

508=22∙127, k1=2; 274=21∙137, k2=1.

=> k=min(k1,k2)=1, a1=max(137,127)=137, b1=min(137,127)=127.

c=137-127=10=21∙5, c1=5, a1=max(b1,c1)=127, b1=min(b1,c1)=5.

c=127-5=122=21∙61, c1=61, a1=61, b1=5.

c=61-5=56=23∙7, c1=7, a1=7, b1=5.

c=7-5=2=21∙1, c1=1, a1=5, b1=1.

c=5-1=4=22∙1, c1=1, a1=1, b1=1.

Ответ: НОД(508,274)=2k∙b1=21∙1=2.

д) a = 210, b = 836.

Решение:

210=21∙105, k1=1; 836=22∙209, k2=2.

=> k=min(k1,k2)=1, a1=max(209,105)=209, b1=min(209,105)=105.

c=209-105=104=23∙13, c1=13, a1=max(b1,c1)=105, b1=min(b1,c1)=13.

c=105-13=92=22∙23, c1=23, a1=23, b1=13.

c=23-13=10=21∙5, c1=5, a1=13, b1=5.

c=13-5=8=23∙1, c1=1, a1=5, b1=1.

c=5-1=4=22∙1, c1=1, a1=1, b1=1.

Ответ: НОД(210,836)=2k∙b1=21∙1=2.

2. Модуль ASIMP.

2.1. Определить примерное количество простых чисел в диапазоне от a до b.

Определить примерное количество простых чисел в диапазоне от a до b, где:

а) a = 1100, b = 16000;

б) a = 4600, b = 35000;

в) a = 4400, b = 34000;

г) a = 2400, b = 13000;

д) a = 2800, b = 52000.

Определить примерное количество простых чисел в диапазоне от a до b, где:

а) a = 1100, b = 16000.

Решение:

Примерное количество простых чисел в диапазоне от 1100 до 16000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1495,76.

Ответ: K ≈ 1495,76.

б) a = 4600, b = 35000.

Решение:

Примерное количество простых чисел в диапазоне от 4600 до 35000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2799,66.

Ответ: K ≈ 2799,66.

в) a = 4400, b = 34000.

Решение:

Примерное количество простых чисел в диапазоне от 4400 до 34000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2734,07.

Ответ: K ≈ 2734,07.

г) a = 2400, b = 13000.

Решение:

Примерное количество простых чисел в диапазоне от 2400 до 13000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1064,01.

Ответ: K ≈ 1064,01.

д) a = 2800, b = 52000.

Решение:

Примерное количество простых чисел в диапазоне от 2800 до 52000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 4435,89.

Ответ: K ≈ 4435,89.

2.2. Какова вероятность того, что наугад выбранное число из диапазона от a до b будет простым.

Какова вероятность того, что наугад выбранное число из диапазона от a до b будет простым, если:

а) a = 2000, b = 19000;

б) a = 3800, b = 41000;

в) a = 510, b = 22000;

г) a = 3500, b = 25000;

д) a = 3700, b = 32000.

Какова вероятность того, что наугад выбранное число из диапазона от a до b будет простым, если:

а) a = 2000, b = 19000.

Решение:

Примерное количество простых чисел в диапазоне от 2000 до 19000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1665,38.

Количество чисел, больших 2000 и меньших 19000, есть 17000. Вероятность случайного выбора простого числа есть

P = 1665,38 / 17000 ≈ 0,1.

Ответ: P ≈ 0,1.

б) a = 3800, b = 41000.

Решение:

Примерное количество простых чисел в диапазоне от 3800 до 41000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3399,15.

Количество чисел, больших 3800 и меньших 41000, есть 37200. Вероятность случайного выбора простого числа есть

P = 3399,15 / 37200 ≈ 0,09.

Ответ: P ≈ 0,09.

в) a = 510, b = 22000.

Решение:

Примерное количество простых чисел в диапазоне от 510 до 22000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2118,46.

Количество чисел, больших 510 и меньших 22000, есть 21490. Вероятность случайного выбора простого числа есть

P = 2118,46 / 21490 ≈ 0,1.

Ответ: P ≈ 0,1.

г) a = 3500, b = 25000.

Решение:

Примерное количество простых чисел в диапазоне от 3500 до 25000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2039,84.

Количество чисел, больших 3500 и меньших 25000, есть 21500. Вероятность случайного выбора простого числа есть

P = 2039,84 / 21500 ≈ 0,09.

Ответ: P ≈ 0,09.

д) a = 3700, b = 32000.

Решение:

Примерное количество простых чисел в диапазоне от 3700 до 32000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2634,45.

Количество чисел, больших 3700 и меньших 32000, есть 28300. Вероятность случайного выбора простого числа есть

P = 2634,45 / 28300 ≈ 0,09.

Ответ: P ≈ 0,09.

2.3. Какова вероятность того, что наугад выбранное нечетное число из диапазона от a до b будет простым.

Какова вероятность того, что наугад выбранное нечетное число из диапазона от a до b будет простым, если:

а) a = 2600, b = 31000;

б) a = 590, b = 23000;

в) a = 4900, b = 52000;

г) a = 3700, b = 20000;

д) a = 3800, b = 21000.

Какова вероятность того, что наугад выбранное нечетное число из диапазона от a до b будет простым, если:

а) a = 2600, b = 31000.

Решение:

Примерное количество простых чисел в диапазоне от 2600 до 31000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2666,91.

Количество чисел, больших 2600 и меньших 31000, есть 28400. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 14200. Вероятность случайного выбора простого числа есть

P = 2666,91 / 14200 ≈ 0,19.

Ответ: P ≈ 0,19.

б) a = 590, b = 23000.

Решение:

Примерное количество простых чисел в диапазоне от 590 до 23000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2197,62.

Количество чисел, больших 590 и меньших 23000, есть 22410. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 11205. Вероятность случайного выбора простого числа есть

P = 2197,62 / 11205 ≈ 0,2.

Ответ: P ≈ 0,2.

в) a = 4900, b = 52000.

Решение:

Примерное количество простых чисел в диапазоне от 4900 до 52000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 4211,98.

Количество чисел, больших 4900 и меньших 52000, есть 47100. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 23550. Вероятность случайного выбора простого числа есть

P = 4211,98 / 23550 ≈ 0,18.

Ответ: P ≈ 0,18.

г) a = 3700, b = 20000.

Решение:

Примерное количество простых чисел в диапазоне от 3700 до 20000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1569,15.

Количество чисел, больших 3700 и меньших 20000, есть 16300. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 8150. Вероятность случайного выбора простого числа есть

P = 1569,15 / 8150 ≈ 0,19.

Ответ: P ≈ 0,19.

д) a = 3800, b = 21000.

Решение:

Примерное количество простых чисел в диапазоне от 3800 до 21000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1649,06.

Количество чисел, больших 3800 и меньших 21000, есть 17200. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 8600. Вероятность случайного выбора простого числа есть

P = 1649,06 / 8600 ≈ 0,19.

Ответ: P ≈ 0,19.

2.4. Какова вероятность того, что наугад выбранное не кратное 3-м число из диапазона от a до b будет простым.

Какова вероятность того, что наугад выбранное не кратное 3-м число из диапазона от a до b будет простым, если:

а) a = 3400, b = 30000;

б) a = 4300, b = 37000;

в) a = 3100, b = 39000;

г) a = 1500, b = 15000;

д) a = 1500, b = 41000.

Какова вероятность того, что наугад выбранное не кратное 3-м число из диапазона от a до b будет простым, если:

а) a = 3400, b = 30000.

Решение:

Примерное количество простых чисел в диапазоне от 3400 до 30000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2491,97.

Количество чисел, больших 3400 и меньших 30000, есть 26600. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 17733,33. Вероятность случайного выбора простого числа есть

P = 2491,97 / 17733,33 ≈ 0,14.

Ответ: P ≈ 0,14.

б) a = 4300, b = 37000.

Решение:

Примерное количество простых чисел в диапазоне от 4300 до 37000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3003,59.

Количество чисел, больших 4300 и меньших 37000, есть 32700. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 21800. Вероятность случайного выбора простого числа есть

P = 3003,59 / 21800 ≈ 0,14.

Ответ: P ≈ 0,14.

в) a = 3100, b = 39000.

Решение:

Примерное количество простых чисел в диапазоне от 3100 до 39000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3303,62.

Количество чисел, больших 3100 и меньших 39000, есть 35900. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 23933,33. Вероятность случайного выбора простого числа есть

P = 3303,62 / 23933,33 ≈ 0,14.

Ответ: P ≈ 0,14.

г) a = 1500, b = 15000.

Решение:

Примерное количество простых чисел в диапазоне от 1500 до 15000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1354,82.

Количество чисел, больших 1500 и меньших 15000, есть 13500. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 9000. Вероятность случайного выбора простого числа есть

P = 1354,82 / 9000 ≈ 0,15.

Ответ: P ≈ 0,15.

д) a = 1500, b = 41000.

Решение:

Примерное количество простых чисел в диапазоне от 1500 до 41000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3655,05.

Количество чисел, больших 1500 и меньших 41000, есть 39500. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 26333,33. Вероятность случайного выбора простого числа есть

P = 3655,05 / 26333,33 ≈ 0,14.

Ответ: P ≈ 0,14.

2.5. Какова вероятность того, что наугад выбранное нечетное и не кратное 3-м число из диапазона от a до b будет простым.

Какова вероятность того, что наугад выбранное нечетное и не кратное 3-м число из диапазона от a до b будет простым, если:

а) a = 1500, b = 25000;

б) a = 1300, b = 34000;

в) a = 2600, b = 36000;

г) a = 2300, b = 46000;

д) a = 4200, b = 18000.

Какова вероятность того, что наугад выбранное нечетное и не кратное 3-м число из диапазона от a до b будет простым, если:

а) a = 1500, b = 25000.

Решение:

Примерное количество простых чисел в диапазоне от 1500 до 25000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2263,63.

Количество чисел, больших 1500 и меньших 25000, есть 23500. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 7833,33. Вероятность случайного выбора простого числа есть

P = 2263,63 / 7833,33 ≈ 0,29.

Ответ: P ≈ 0,29.

б) a = 1300, b = 34000.

Решение:

Примерное количество простых чисел в диапазоне от 1300 до 34000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3077,23.

Количество чисел, больших 1300 и меньших 34000, есть 32700. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 10900. Вероятность случайного выбора простого числа есть

P = 3077,23 / 10900 ≈ 0,28.

Ответ: P ≈ 0,28.

в) a = 2600, b = 36000.

Решение:

Примерное количество простых чисел в диапазоне от 2600 до 36000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3100,77.

Количество чисел, больших 2600 и меньших 36000, есть 33400. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 11133,33. Вероятность случайного выбора простого числа есть

P = 3100,77 / 11133,33 ≈ 0,28.

Ответ: P ≈ 0,28.

г) a = 2300, b = 46000.

Решение:

Примерное количество простых чисел в диапазоне от 2300 до 46000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3987,36.

Количество чисел, больших 2300 и меньших 46000, есть 43700. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 14566,67. Вероятность случайного выбора простого числа есть

P = 3987,36 / 14566,67 ≈ 0,27.

Ответ: P ≈ 0,27.

д) a = 4200, b = 18000.

Решение:

Примерное количество простых чисел в диапазоне от 4200 до 18000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1333,66.

Количество чисел, больших 4200 и меньших 18000, есть 13800. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 4600. Вероятность случайного выбора простого числа есть

P = 1333,66 / 4600 ≈ 0,29.

Ответ: P ≈ 0,29.

2.6. Сколько чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

Сколько чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 4400, b = 32000, p = 0,7;

б) a = 600, b = 41000, p = 0,99;

в) a = 3500, b = 43000, p = 0,93;

г) a = 1600, b = 49000, p = 0,5;

д) a = 1000, b = 34000, p = 0,8.

Сколько чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 4400, b = 32000, p = 0,7.

Решение:

Примерное количество простых чисел в диапазоне от 4400 до 32000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2560,31.

Количество чисел, больших 4400 и меньших 32000, есть 27600. Вероятность случайного выбора простого числа есть

P = 2560,31 / 27600 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 12,37 => n=13.

Ответ: требуется 13 испытаний.

б) a = 600, b = 41000, p = 0,99.

Решение:

Примерное количество простых чисел в диапазоне от 600 до 41000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3766,36.

Количество чисел, больших 600 и меньших 41000, есть 40400. Вероятность случайного выбора простого числа есть

P = 3766,36 / 40400 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 47,06 => n=48.

Ответ: требуется 48 испытаний.

в) a = 3500, b = 43000, p = 0,93.

Решение:

Примерное количество простых чисел в диапазоне от 3500 до 43000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3601,49.

Количество чисел, больших 3500 и меньших 43000, есть 39500. Вероятность случайного выбора простого числа есть

P = 3601,49 / 39500 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 27,82 => n=28.

Ответ: требуется 28 испытаний.

г) a = 1600, b = 49000, p = 0,5.

Решение:

Примерное количество простых чисел в диапазоне от 1600 до 49000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 4320,35.

Количество чисел, больших 1600 и меньших 49000, есть 47400. Вероятность случайного выбора простого числа есть

P = 4320,35 / 47400 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 7,25 => n=8.

Ответ: требуется 8 испытаний.

д) a = 1000, b = 34000, p = 0,8.

Решение:

Примерное количество простых чисел в диапазоне от 1000 до 34000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3113,78.

Количество чисел, больших 1000 и меньших 34000, есть 33000. Вероятность случайного выбора простого числа есть

P = 3113,78 / 33000 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 16,24 => n=17.

Ответ: требуется 17 испытаний.

2.7. Сколько нечетных чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

Сколько нечетных чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 3400, b = 14000, p = 0,75;

б) a = 1500, b = 32000, p = 0,85;

в) a = 2900, b = 36000, p = 0,93;

г) a = 850, b = 47000, p = 0,91;

д) a = 1300, b = 44000, p = 0,997.

Сколько нечетных чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 3400, b = 14000, p = 0,75.

Решение:

Примерное количество простых чисел в диапазоне от 3400 до 14000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1048,33.

Количество чисел, больших 3400 и меньших 14000, есть 10600. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 5300. Вероятность случайного выбора простого числа есть

P = 1048,33 / 5300 ≈ 0,2.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 6,29 => n=7.

Ответ: требуется 7 испытаний.

б) a = 1500, b = 32000, p = 0,85.

Решение:

Примерное количество простых чисел в диапазоне от 1500 до 32000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2879,68.

Количество чисел, больших 1500 и меньших 32000, есть 30500. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 15250. Вероятность случайного выбора простого числа есть

P = 2879,68 / 15250 ≈ 0,19.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 9,07 => n=10.

Ответ: требуется 10 испытаний.

в) a = 2900, b = 36000, p = 0,93.

Решение:

Примерное количество простых чисел в диапазоне от 2900 до 36000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3067,67.

Количество чисел, больших 2900 и меньших 36000, есть 33100. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 16550. Вероятность случайного выбора простого числа есть

P = 3067,67 / 16550 ≈ 0,19.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 12,97 => n=13.

Ответ: требуется 13 испытаний.

г) a = 850, b = 47000, p = 0,91.

Решение:

Примерное количество простых чисел в диапазоне от 850 до 47000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 4242,87.

Количество чисел, больших 850 и меньших 47000, есть 46150. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 23075. Вероятность случайного выбора простого числа есть

P = 4242,87 / 23075 ≈ 0,18.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 11,85 => n=12.

Ответ: требуется 12 испытаний.

д) a = 1300, b = 44000, p = 0,997.

Решение:

Примерное количество простых чисел в диапазоне от 1300 до 44000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3933,94.

Количество чисел, больших 1300 и меньших 44000, есть 42700. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 21350. Вероятность случайного выбора простого числа есть

P = 3933,94 / 21350 ≈ 0,18.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)n ≥ p. Тогда n ≥ log(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 28,52 => n=29.

Ответ: требуется 29 испытаний.


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница