Общая проблема заключается в определении основной факторизации числа. Подход с использованием грубой силы — это пробное деление ( Википедия , Академия Хана ), но оно требует больших усилий, если необходимо учитывать несколько чисел.
Одним из широко используемых решений является сито Эратосфена ( Wikipedia , Math World ). Сито Эратосфена легко модифицировать так, чтобы оно содержало наибольший простой множитель каждого составного числа. Это делает его чрезвычайно дешевым для последующего вычисления простой факторизации чисел.
Если нас заботит только первичность, мы можем использовать растровое изображение с ситом Эратосфена или сито Аткина ).
(Замечание: для ясности я опускаю общие оптимизации, которые вытекают из того факта, что простое число всегда равно «1 mod 2, n> 2» и «1 или 5 mod 6, n> 5». Это может существенно уменьшить количество памяти, необходимое для сита.)
|
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
public enum SieveOfEratosthenes { SIEVE; private int[] sieve; private SieveOfEratosthenes() { // initialize with first million primes - 15485865 // initialize with first 10k primes - 104729 sieve = initialize(104729); } /** * Initialize the sieve. */ private int[] initialize(int sieveSize) { long sqrt = Math.round(Math.ceil(Math.sqrt(sieveSize))); long actualSieveSize = (int) (sqrt * sqrt); // data is initialized to zero int[] sieve = new int[actualSieveSize]; for (int x = 2; x < sqrt; x++) { if (sieve[x] == 0) { for (int y = 2 * x; y < actualSieveSize; y += x) { sieve[y] = x; } } } return sieve; } /** * Is this a prime number? * * @FIXME handle n >= sieve.length! * * @param n * @return true if prime * @throws IllegalArgumentException * if negative number */ public boolean isPrime(int n) { if (n < 0) { throw new IllegalArgumentException("value must be non-zero"); } boolean isPrime = sieve[n] == 0; return isPrime; } /** * Factorize a number * * @FIXME handle n >= sieve.length! * * @param n * @return map of prime divisors (key) and exponent(value) * @throws IllegalArgumentException * if negative number */ private Map<Integer, Integer> factorize(int n) { if (n < 0) { throw new IllegalArgumentException("value must be non-zero"); } final Map<Integer, Integer> factors = new TreeMap<Integer, Integer>(); for (int factor = sieve[n]; factor > 0; factor = sieve[n]) { if (factors.containsKey(factor)) { factors.put(factor, 1 + factors.get(factor)); } else { factors.put(factor, 1); } n /= factor; } // must add final term if (factors.containsKey(n)) { factors.put(n, 1 + factors.get(n)); } else { factors.put(n, 1); } return factors; } /** * Convert a factorization to a human-friendly string. The format is a * comma-delimited list where each element is either a prime number p (as * "p"), or the nth power of a prime number as "p^n". * * @param factors * factorization * @return string representation of factorization. * @throws IllegalArgumentException * if negative number */ public String toString(Map factors) { StringBuilder sb = new StringBuilder(20); for (Map.Entry entry : factors.entrySet()) { sb.append(", "); if (entry.getValue() == 1) { sb.append(String.valueOf(entry.getKey())); } else { sb.append(String.valueOf(entry.getKey())); sb.append("^"); sb.append(String.valueOf(entry.getValue())); } } return sb.substring(2); }} |
Этот код имеет существенный недостаток — он потерпит неудачу, если запрошенное число выходит за пределы допустимого диапазона. Это легко исправить — мы можем динамически изменить размер сита по мере необходимости. Мы используем блокировку, чтобы гарантировать, что многопоточные вызовы не переводят решето в промежуточное состояние. Мы должны быть осторожны, чтобы не попасть в тупик между блокировками чтения и записи.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
private final ReadWriteLock lock = new ReentrantReadWriteLock(); /** * Initialize the sieve. This method is called when it is necessary to grow * the sieve. */ private void reinitialize(int n) { try { lock.writeLock().lock(); // allocate 50% more than required to minimize thrashing. initialize((3 * n) / 2); } finally { lock.writeLock().unlock(); } } /** * Is this a prime number? * * @param n * @return true if prime * @throws IllegalArgumentException * if negative number */ public boolean isPrime(int n) { if (n < 0) { throw new IllegalArgumentException("value must be non-zero"); } if (n > sieve.length) { reinitialize(n); } boolean isPrime = false; try { lock.readLock().lock(); isPrime = sieve[n] == 0; } finally { lock.readLock().unlock(); } return isPrime; } /** * Factorize a number * * @param n * @return map of prime divisors (key) and exponent(value) * @throws IllegalArgumentException * if negative number */ private Map<Integer, Integer> factorize(int n) { if (n < 0) { throw new IllegalArgumentException("value must be non-zero"); } final Map<Integer, Integer> factors = new TreeMap<Integer, Integer>(); try { if (n > sieve.length) { reinitialize(n); } lock.readLock().lock(); for (int factor = sieve[n]; factor > 0; factor = sieve[n]) { if (factors.containsKey(factor)) { factors.put(factor, 1 + factors.get(factor)); } else { factors.put(factor, 1); } n /= factor; } } finally { lock.readLock().unlock(); } // must add final term if (factors.containsKey(n)) { factors.put(n, 1 + factors.get(n)); } else { factors.put(n, 1); } return factors; } |
Итерируемые циклы <Integer> и foreach
В реальном мире часто проще использовать цикл foreach (или явный итератор), чем проверять элемент таблицы за элементом. К счастью, легко создать итератор, который построен на основе нашего саморазвитого сита.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
/** * @see java.util.List#get(int) * * We can use a cache of the first few (1000? 10,000?) primes * for improved performance. * * @param n * @return nth prime (starting with 2) * @throws IllegalArgumentException * if negative number */ public Integer get(int n) { if (n < 0) { throw new IllegalArgumentException("value must be non-zero"); } Iterator<Integer> iter = iterator(); for (int i = 0; i < n; i++) { iter.next(); } return iter.next(); } /** * @see java.util.List#indexOf(java.lang.Object) */ public int indexOf(Integer n) { if (!isPrime(n)) { return -1; } int index = 0; for (int i : sieve) { if (i == n) { return index; } index++; } return -1; } /** * @see java.lang.Iterable#iterator() */ public Iterator<Integer> iterator() { return new EratosthenesListIterator(); } public ListIterator<Integer> listIterator() { return new EratosthenesListIterator(); } /** * List iterator. * * @author Bear Giles <[email protected]> */ static class EratosthenesListIterator extends AbstractListIterator<Integer> { int offset = 2; /** * @see com.invariantproperties.projecteuler.AbstractListIterator#getNext() */ @Override protected Integer getNext() { while (true) { offset++; if (SIEVE.isPrime(offset)) { return offset; } } // we'll always find a value since we dynamically resize the sieve. } /** * @see com.invariantproperties.projecteuler.AbstractListIterator#getPrevious() */ @Override protected Integer getPrevious() { while (offset > 0) { offset--; if (SIEVE.isPrime(offset)) { return offset; } } // we only get here if something went horribly wrong throw new NoSuchElementException(); } }} |
ВАЖНО: код:
|
1
|
for (int prime : SieveOfEratosthenes.SIEVE) { ... } |
по сути бесконечный цикл. Он остановится только после того, как JVM исчерпает пространство кучи при выделении нового сита.
На практике это означает, что максимальное простое число, которое мы можем поддерживать в сите, составляет около 1 ГБ. Для этого требуется 4 ГБ с 4-байтовыми значениями. Если мы заботимся только о простоте и используем общую оптимизацию, то 4 ГБ могут хранить информацию о значениях 64 ГБ. Для простоты мы можем назвать это от 9 до 10 цифр (основание 10).
Что если мы поместим наше сито на диск?
Нет причины, по которой сито должно оставаться в памяти. Наш итератор может спокойно загружать значения с диска вместо кэша в памяти. Диск объемом 4 ТБ, доступ к которому, вероятно, осуществляется в необработанном режиме, может показаться, что размер нашего сита увеличился до 14–15 цифр (основание 10). На самом деле это будет немного меньше, потому что нам придется удвоить размер наших примитивных типов с int на long , а затем, вероятно, на еще больший формат.
Больше! Больше! Больше!
Мы можем значительно увеличить эффективный размер нашего сита, отметив, что нам нужно только вычислить sqrt (n) для инициализации сита из n значений. Мы можем перевернуть это и сказать, что полностью заполненное сито из n значений может быть использовано для заполнения другого сита из n 2 значений. В этом случае мы хотим заполнить только группу, а не полное сито n 2 . Наше сито в памяти теперь может охватывать значения примерно до 40-значных чисел (основание 10), а сито на основе диска переходит к 60-значным числам (основание 10), минус пространство, необходимое для больших значений.
Нет никаких причин, по которым этот подход не может быть принят еще дальше — используйте маленькое сито для загрузки большего переходного сита и используйте его, в свою очередь, для заполнения еще большего сита.
Но сколько времени это займет?
Да, есть руб. Стоимость инициализации сита из n значений составляет O (n 2 ) . Вы можете использовать различные настройки, чтобы уменьшить константы, но в конце дня вы посещаете каждый узел один раз ( O (n) ), а затем посещаете некоторое скользящее значение, пропорциональное n за пределами каждой из этих точек. Для этого стоит проблема, когда сохранение архитектуры кэша ЦП может иметь большое значение.
В практическом плане любая современная система должна быть способна создать сито, содержащее первый миллион простых чисел, в течение нескольких секунд. Поднимите сито до первого миллиарда простых чисел, и время, вероятно, подскочило до недели, возможно, месяца, если ограниченное пространство кучи JVM вынуждает нас интенсивно использовать диск. Мой инстинкт инстинкта заключается в том, что ферме серверов понадобятся месяцы или годы, чтобы заполнить диск с ТБ
Зачем беспокоиться ?
Для большинства из нас основным выводом является демонстрация того, как начать сборку с небольшого семени, скажем, сита с n = 1000 , и прозрачно выращивать его по мере необходимости. Это легко с простыми числами, но не сложно представить себе тот же подход, который используется, ну, в RSS-каналах. Мы привыкли думать об итераторах как о скучном аспекте коллекций, но на самом деле они дают нам большую гибкость, когда используются как часть Iterable.
Существует также практическая причина для большого простого сита — факторинг больших количеств. Существует несколько хороших алгоритмов для учета больших чисел, но они дорогие — даже «маленькие» числа могут занимать месяцы или годы в ферме серверов. Вот почему первым шагом всегда является пробное деление с «маленькими» простыми числами, что может занять один день.
Исходный код
Хорошая новость в том, что я опубликовал исходный код для этого … и плохая новость в том, что это часть постоянного рисования, когда я занимаюсь проблемами Project Euler. (Здесь нет решений — это просто исследование идей, вдохновленных проблемами. Так что код немного грубоват и не должен использоваться, чтобы решить, следует ли мне приводить меня на собеседование (если вы не впечатлены): http : //github.com/beargiles/projecteuler.
| Ссылка: | Получите бесконечный список простых чисел в Java от нашего партнера по JCG Bear Giles в блоге Invariant Properties . |