If you find this site interesting, it has learned you 2-3 tips, may be it made you laugh or cry (uh?). Please support it by sending us some coin at the following three addresses, thank you. Bitcoin adress Litecoin adress Dodgecoin adress ## Trial division## The principle
As its name suggests, the method "Trial Division" allows to find a factor
of a given integer by trying to divide this number by all others are inferior. ## First implementationFrom a computational point of view, so we need several things : - An array of Boolean 2 to N as to whether a number is prime or not.
- A loop over the numbers from 1 to N which we will apply the test of Trial division.
- A second nested loop trying divisions with another number ranging from 1 to N.
- Suppose p > √n and q > √n
Means that p * q > √n * √n but √n * √n = n Thus p * q > n hence contradiction - Suppose p > √n and q > √n
Means that there are two positive numbers x and y such as p = x + √n and q = y + √n If we multiply p by q we have p * q = n = (x + √n) * (y + √n) = xy + √n(x * y) + n ie : xy + √n(x * y) = 0 But all numbers of this equation are positive, we can not obtain 0 hence contradiction
private static final int MAX = 10000000;private static boolean[] array = new boolean[MAX];//--// array[2] = true;for (int i = 3; i < MAX; i += 2) {sqrtN = Math.round(Math.sqrt(i)) + 1; premier = true;for (int j = 3; j < sqrtN; j += 2) {if ((i % j) == 0) {premier = false;break;} } array[i] = premier; }
So ! Let us not hide the results are very bad for the moment because in comparison with
the sieve of Eratosthenes we have 0.906 seconds against 0.031 for the first non-optimized
implementation, which is 30 times longer ! Worse, I stopped the test for 100 million
because the cpu from my old AMD 3200+ 6 years of age ran a little too much for my taste... ## Second implementation
To improve the time it is absolutely necessary to succeed to make less division than the first
implementation and for that we go from one observation : private static final int MAX = 10000000;private static final int ARRAY_SIZE = (int) Math.round((MAX * 1.1) / Math.log(MAX));private static int[] array = new int[ARRAY_SIZE];//--// int pos = 0;array[pos++] = 2; for (int i = 3; i < MAX; i += 2) {sqrtN = Math.round(Math.sqrt(i)) + 1; for (int j = 0; j < pos; j++) {int value = array[j];if (value > sqrtN) {premier = true;break;} if ((i % value) == 0) {premier = false;break;} } if (premier) {array[pos++] = i; } }
Indeed we won a lot of time with this optimization! But we are still far from the Sieve of Eratosthenes... Try to do better. source ## Third implementation
To optimize the algorithm, we are going to have the same approach for the optimization of the Sieve
of Atkin, we will adress one of the operators which is an expensive operation in computing time.
Here it will be the square root. private static final int MAX = 100000000;private static final int ARRAY_SIZE = (int) Math.round((MAX * 1.1) / Math.log(MAX));private static int[] array = new int[ARRAY_SIZE];//--// int pos = 0;array[pos++] = 2; int sqrtN = 3;int countSqrtN = 2;for (int i = 3; i < MAX; i += 2) {for (int j = 0; j < pos; j++) {int value = array[j];if (value > sqrtN) {premier = true;break;} if ((i % value) == 0) {premier = false;break;} } if (premier) {array[pos++] = i; } if (--countSqrtN == 0) {countSqrtN = sqrtN; sqrtN++; } }
Gradually we improve the algorithm but this time we reach at the limit of optimization. source ## In conclusion
So we see that we are very far by using the Trial division compared to others sieves and
despite 3 optimizations we have a ratio of 1 to 11 with a non-optimized Sieve of Eratosthenes.
We do not even tickled the sieves... |