Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 35

Любое число может быть представлено как произведение простых чисел. Например: 84 = 2² × 3¹ × 5⁰ × 7¹ × 11⁰ × 13⁰ × 17⁰ ×…

Делимость

Из закона простых чисел следует, что если xделится на y(будем записывать это условие как x\y или mod(y, x) = 0), то все простые числа, входящие в разложение на множители числа x, должны присутствовать в разложении на множители числа y. Рассмотрим пример:

Пусть x = 2^j0 * 3^j1 * 5^j2 * 7^j3 * 11^j4 *…

Пусть y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * 11^k4 *…

Если x\y, тогда для всех i выполняется неравенство ji <= ki.

Наибольший общий делитель x и y:

gcd(x, y) = 2^{min(j0, k0)} * 3^{min(j1, k1)} * 5^{min(j2, k2)} *…

Наименьшее общее кратное x и y:

lcm(x, y) = 2^{max(j0, k0)} * 3^{max(j1, k1)} * 5^{max(j2, k2)} *…

Попробуйте сами решить забавную задачку: найдите произведение НОД и НОК (gcd *lcm):

gcd * lcm = 2^{min(j0, k0)} * 2^{max(j0, k0)} * 3^{min(j1, k1)} * 3^{max(j1, k1)} *…

= 2^{min(j0, k0) + max(j0, k0) * 3min(j1, k1) + max(j1, k1)} *…

= 2^min(j0,, ^k1) *…

= 2^{j0 + k0} * 3^{j1 + k1} *…

= 2^j0 * 2^k0 * 3^j1 * 3^k1 *…

= xy

Является ли число простым

Этот вопрос настолько часто встречается, что о нем необходимо упомянуть. Для этого достаточно проверить делимость в цикле от 2 до n-1:

1 boolean primeNaive(int n) {

2 if (n < 2) {

3 return false;

4 }

5 for (int i = 2; i < n; i++) {

6 if (n % i == 0) {

7 return false;

8 }

9 }

10 return true;

11 }

Небольшое, но немаловажное улучшение – цикл можно ограничить квадратным корнем из n.

1 boolean primeSlightlyBetter(int n) {

2 if (n < 2) {

3 return false;

4 }

5 int sqrt = (int) Math.sqrt(n);

6 for (int i = 2; i <= sqrt; i++) {

7 if (n % i == 0) return false;

8 }

9 return true;

10 }

Квадратного корня достаточно, поскольку для каждого числа, которое делится на n без остатка, есть дополнение b, такое что a*b=n. Если a>sqrt, то b<sqrt (поскольку sqrt * sqrt = n). a нам не понадобится, так как для проверки n на простоту мы уже сверились с b.

На самом деле все, что нужно сделать, – это проверить, делится ли n на простые числа. И тут появляется решето Эратосфена.

Список простых чисел: решето Эратосфена

Решето Эратосфена – эффективный способ генерации списка простых чисел. Он работает, распознавая все составные числа, которые делятся на простые числа.

Начнем с генерации списка всех чисел, не превышающих заданного значения max. Можно сразу вычеркнуть четные числа. Затем найти ближайшее простое число и вычеркнуть все числа, кратные ему. Последовательно исключая все числа, кратные 2, 3, 5, 7, 11 и т. д., мы получим список простых чисел, лежащих в диапазоне от 2 до max.

Представленный далее код реализует решето Эратосфена:

1 boolean[] sieveOfEratosthenes(int max) {

2 boolean[] flags = new boolean[max + 1];

3 int count = 0;

4

5 init(flags); // Устанавливаем все флаги в true (кроме 0 и 1)

6 int prime = 2;

7

8 while (prime <= max) {

9 /* Вычеркиваем оставшуюся часть произведений простых чисел */

10 crossOff(flags, prime);

11

12 /* Находим следующее истинное значение */

13 prime = getNextPrime(flags, prime);

14

15 if (prime >= flags.length) {

16 break;

17 } 18 }

19 20 return flags;

21 }

22

23 void crossOff(boolean[] flags, int prime) {

24 /* Вычеркиваем оставшуюся часть произведений простых чисел. Мы начинаем

25 * с (prime*prime), потому что, если существует k * prime,

26 * где k < prime, это значение должно быть вычеркнуто

27 * на предыдущей итерации. */

28 for (int i = prime * prime; i < flags.length; i += prime) {

29 flags[i] = false;

30 }

31 }

32

33 int getNextPrime(boolean[] flags, int prime) {

34 int next = prime + 1;

35 while (next < flags.length &&!flags[next]) {

36 next++;

37 }

38 return next;

39 }

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

Теория вероятностей – довольно сложная тема, но она основана на нескольких достаточно логичных законах. Посмотрите на диаграмму Венна, визуализирующую два события – A и B. Области двух кругов соответствуют относительным вероятностям событий, а область пересечения – вероятности события {A and B}.

Вероятность события {A and B}

Представьте, что вы бросили стрелку дартса в диаграмму Венна. Какова вероятность, что вы попадете в пересечение кругов А и B? Если вы знаете вероятность попадания в область А и знаете, какой процент круга А перекрывается кругом B (то есть вероятность того, что вы попадете в B, если попали в А), то вероятность события P{A and B} можно записать как:

P(A and B) = P(B given A) P(A)

Например, предположим, что мы выбрали число из интервала от 1 до 10 (включительно). Какова вероятность того, что выбранное число окажется четным и будет принадлежать интервалу от 1 до 5. Вероятность того, что выбранное число принадлежит диапазону от 1 до 5, составляет 50 %, а вероятность того, что это число окажется четным, – 40 %. Так, подсчитаем вероятность данного события:

P(x is even and x <= 5)

= P(x is even given x <= 5) P(x <= 5)

= (2/5) * (1/2)

= 1/5

Вероятность события {A or B}

Рассмотрим другой случай – вероятность попадания в область A или B – P{A or B}. Если вы знаете вероятности попадания в каждую область и вероятность попадания в пересечение областей, тогда

P(A or B) = P(A) + P(B) – P(A and B)

С точки зрения логики все корректно – нам нужно только сложить площади обоих кругов и избавиться от двойного наложения в области пересечения. Давайте визуализируем эту задачу с помощью диаграммы Венна:

Например, предположим, что мы выбрали число из интервала от 1 до 10 (включи тельно). Какова вероятность того, что число окажется четным или будет принадлежать диапазону от 1 до 5? Вероятность того, что число является четным, – 50 %. Вероятность того, что число принадлежит интервалу от 1 до 5, также составляет 50 %. Вероятность того, что число четное и принадлежит заданному интервалу, мы уже вычислили в предыдущем примере, она составляет 20 %.

P(x is even or x <=5)

= P(x is even) + P(x <= 5) – P(x is even and x <= 5)

= (1/2) + (1/2) – (1/5)

= 4/5

Теперь сформулировать правила для независимых и взаимоисключающих событий не составит труда.

Независимость событий

Если A и B независимы (наступление одного события не изменяет вероятность наступления другого), то P(A and B) =P(A)P(B). Это правило с очевидностью следует из того, что P(B given A) =P(B), при условии, что событие A никак не связано с B.

Взаимоисключающие события

Если A и B являются взаимоисключающими (если одно событие произошло, то другое произойти не может), то P(Aor B) =P(A)+ P(B) (поскольку P(AandB) = 0).

Многие путают независимые и взаимоисключающие события. На самом деле два события не могут быть одновременно независимыми и взаимоисключающими (конечно, если вероятность событий больше 0). Почему? Для взаимоисключающих событий факт свершения одного события означает, что второе невозможно. Независимость означает, что реализация одного события никак не влияет на другое. Таким образом, два события с ненулевыми вероятностями не могут быть и взаимоисключающими, и независимыми.

Если одно или оба события имеют нулевую вероятность (то есть события невозможны), то события являются и независимыми, и взаимоисключающими. Это следует из определений независимых и взаимоисключающих событий.