 mersenneforum.org Need an assessment and help regarding prime numbers.
 Register FAQ Search Today's Posts Mark Forums Read  2022-01-05, 13:24 #1 TimoKinnunen   "Timo Kinnunen" Jan 2022 Sweden 2 Posts Need an assessment and help regarding prime numbers. I made an algorithm (2000 primes per minute) that without dividing (see example below) produces all primes of 2,3,5,7,... I think it is revolutionary. But I don't know and need your expertise here. If you say that technique already exists, I have already been remedied. Have you heard of an algorithm that produces prime numbers without the usual test with "a % b == 0"? Thank you if you answered that question. Of course, I haven't found anything on the net. Is it possible to become a Doctor in the subject? It's fast because the answer already exists! // List primeNumberItemsList = await App.PrimeNumberRepo.GetAllPrimeNumberItemsAsync(); // //calculate primenumbers the old way // foreach (PrimeNumberItem primeNumberItem in primeNumberItemsList) // { // bool isPrimeNumber = true; // for (int i = 2; i < int.Parse(primeNumberItem.PrimeNumber); i++) // { // if (int.Parse(primeNumberItem.PrimeNumber) % i == 0) // { // isPrimeNumber = false; // break; // } // } // }   2022-01-05, 13:30   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

656210 Posts Quote:
 Originally Posted by TimoKinnunen ... without dividing (see example below) ... // if (int.Parse(primeNumberItem.PrimeNumber) % i == 0) ...
% is just a division in disguise. So your code does use division.

Your code does what is known as trial factoring, TF for short. It isn't revolutionary.

Last fiddled with by retina on 2022-01-05 at 13:32   2022-01-05, 14:31 #3 Uncwilly 6809 > 6502   """"""""""""""""""" Aug 2003 101×103 Posts 2·33·197 Posts 2000 primes per minute in the lower realms does not sound fast.   2022-01-05, 14:39   #4
axn

Jun 2003

5,387 Posts Quote:
 Originally Posted by TimoKinnunen I made an algorithm
Well... post your algorithm. Don't post "old way". We know old way. We know more "old ways" than you have heard of. Just post your algorithm and we'll tell you if its already known / good / bad.   2022-01-05, 14:45 #5 kruoli   "Oliver" Sep 2017 Porta Westfalica, DE 44016 Posts Code: private static int Gcd(int a, int b) { while (a != b) { if (a > b) { a -= b; } else { b -= a; } } return a; } var primes = new List(); primes.Add(2); for (int i = 3; i < limit; i += 2) { foreach (int prime in primes) { if (Gcd(prime, i) > 1) { goto not_prime; } } primes.Add(i); not_prime: ; } This is without division, multiplication and modulo. I bet it is faster than 2000 primes per minute up to a limit.   2022-01-05, 18:44   #6
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

1A1116 Posts Welcome to GIMPS (assuming you're here in good faith).
Quote:
 Originally Posted by TimoKinnunen I made an algorithm (2000 primes per minute) that without dividing (see example below) produces all primes of 2,3,5,7,... I think it is revolutionary.
What's revolutionary? Post your source. Document your hardware, software, and operands range for which 2000 primes/minute was achieved.
Show us in detail how what you have done is superior in what respect to any or all of the code examples at
http://rosettacode.org/wiki/Primalit...on%27s_theorem and http://rosettacode.org/wiki/Primality_by_trial_division
If I recall correctly, 2000 very small primes/minute was unremarkable for personal computers of 40 years ago doing simple sieving.

Last fiddled with by kriesel on 2022-01-05 at 18:46   2022-01-06, 01:23 #7 kriesel   "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 667310 Posts The old way seems deliberately constructed to be inefficient. It's perhaps asking a lot of an optimizing compiler to undo that. Code: List primeNumberItemsList = await App.PrimeNumberRepo.GetAllPrimeNumberItemsAsync(); //calculate prime numbers the old way foreach (PrimeNumberItem primeNumberItem in primeNumberItemsList) { bool isPrimeNumber = true; for (int i = 2; i < int.Parse(primeNumberItem.PrimeNumber); i++) { if (int.Parse(primeNumberItem.PrimeNumber) % i == 0) { isPrimeNumber = false; break; } } } int.Parse is string to int conversion. Repeatedly on the same operand. Inside a for loop. That's properly done once outside the loop. i increments by one, testing for factors of 2,3,4,5,6,7, ..., number being tested. Not odds only with the special case of 2 handled separately, not using previously sieved primes only, not using upper limit of sqrt(number under test), not using wheel, etc etc etc. Let's see, 2000 primes/minute ~33.3/second from the OP. I forgot to include Sieve of Eratosthenes earlier. http://rosettacode.org/wiki/Sieve_of...sthenes#Chapel The Chapel output corresponds to ~383,080,366.65 primes/minute. Code: The first 25 primes are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Count of primes to a million is: 78498. Found 50847534 primes up to 1,000,000,000 in 7964.05 milliseconds. The alternate odds-only bit-packed version corresponds to 12,686. primes per MILLISECOND. Multithreaded Chapel 128.279 msec, ~396. primes/ MICROsecond. The Fortran result 219 msec for up to a billion on Intel Skylake i5-6500 CPU at 3.2 GHz multithreaded with four cores, corresponds to ~232,180,520 primes/sec. Plus there's an estimated near-fourfold and a near-double optimization untested. http://rosettacode.org/wiki/Sieve_of...thenes#Fortran where it's noted to then get adequate timing, a range to 10 billion is more appropriate than 1 billion. That would put multithreaded Fortran in the gigaprimes/sec range. Faster way with Haskell: 1.085 seconds, corresponding to 46,864,087./second on Sky Lake i5-2500 CPU @ 3.6 GHz (turbo boost for single threaded) Single threaded NIM up to a billion in 0.793 sec, with untested further near-four-fold and two-fold optimizations, & multithreading unused. And all the preceding is without getting into the superior TF parallelism performance available on GPUs. Last fiddled with by kriesel on 2022-01-06 at 01:36   2022-01-17, 16:41 #8 TimoKinnunen   "Timo Kinnunen" Jan 2022 Sweden 28 Posts Hunting prime numbers with TimoEratosthenes algorithm Inventor of algorithm and author: Timo Kinnunen born 06/30/1956. Subject: Programming, mathematics, prime number. Date: 01/15/2022. Algorithm was born at 12/28/2021 in Finland. Introduction What I know this is first time this kind of algorithm is presented by anybody to public. Traversing x-axis will give prime number candidates and decision is made whether it is a prime number or not using Erathostenes sieve (“knock out” those prime number candidates that can’t be prime numbers). No division is needed. Biggest known Mersenne prime number has 24 million digits. With a database table having three columns (Id, PrimeNumber, ForwardX) where PrimeNumber column and ForwardX column have capacity of 24 million characters, it is possible to bypass biggest known prime number in acceptable time with a powerful super-computer. One known prime number took 14 years to compute. TimoEratosthenes algorithm needs to know as starting point that 3 is prime number. This is enough to reveal all of prime numbers! The numbers have it. The numbers have it. Look at x-axis! Traverse the x-axis! Meaningful cryptography needs prime numbers with 400 digits. Eratosthenes sieve the old way can produce prime numbers up to 8 digits length on home computer. The technique is wrong, and computer’s resources are limited. I recommend TimoEratosthenes algorithm instead when computer’s resources are not limited. Method Showing Eratosthenes sieve as a program. Explaining TimoEratosthes algorithm with guidelines to understanding. Showing TimoEratosthenes algorithm as program. Conclusion. Programming environment All programs are written in C# using Microsoft Visual Studio 2022 and can therefore be reproduced and studied. Eratosthenes sieve the old way Greek Eratosthenes lived around 240 B.C. And hunting primes has gone on for about 2460 years among mathematicians. An example of division with modulus (%) when hunting prime numbers is below. This is the old way. When size of primeNumberCandidate number grows it takes more divisions to decide if primeNumberCandidate is prime number. Code: using System; namespace OldEratosthenes { internal class Program { static void Main(string[] args) { int primeNumberCandidate = 2; int counter = 0; while (true) { bool isPrimeNumber = true; for (int divisor = 2; divisor <= primeNumberCandidate / 2; divisor++) { if (primeNumberCandidate % divisor == 0) { isPrimeNumber = false; break; } } primeNumberCandidate++; if (!isPrimeNumber) { continue; } counter++; if (counter % 1000 == 0) { Console.Clear(); Console.Write($"Prime number is {primeNumberCandidate}. Number of primenumbers is {counter}."); } } } } } Hunting prime numbers with TimoEratosthenes algorithm There has not been a clear understanding of where prime numbers appear on the line y=2*x+1. Focus has been to find prime numbers among prime numbers. And I think that forest is not visible because of all trees. Another approach is shown here. Think of x-axis of natural, positive numbers greater than zero and corresponding y=2*x+1 value as prime number candidate. Use Eratosthenes sieve to decide if prime number candidate is prime number. Knowing two first prime numbers 2 and 3 is enough. The numbers have it! Or knowing 3 as prime number is enough to calculate rest of prime numbers! The numbers have it! Considering natural, positive numbers greater than zero and a line y=2*x+1 then all prime numbers reside on the line except for two (2). Two is a special case and don’t fit on line y=2*x+1. Traversing x-axis from 1 to 2 to 3 and so on will reveal the magic prime numbers by “knocking out” prime number candidates and leaving prime numbers! We have database table (or collection) with columns Id, PrimeNumber and ForwardX at hand. Add one record: PrimeNumber=2, ForwardX=0. Special case. 2 is prime number. Id=1, PrimeNumber=2, ForwardX=0. Let x=1. Prime number candidate that corresponds to x=1 is 2*1+1=3. And forwardx is (3*3 -1)/2=4 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=4 it is “knocked out”. Is prime number candidate 3 prime number? Let us find out. Look through all previous records in database table for 1==ForwardX. Database table contains 1 record and no records match query 1==ForwardX. 3 is therefore prime number. We know that when x=4 prime number candidate is 2*4+1=9 and cannot be prime number. Add prime number candidate 3 to database table PrimeNumber=3, ForwardX=4. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=4. Let x=2. Prime number candidate that corresponds to x=2 is 2*2+1=5. And forwardx is (5*5 -1)/2=12 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=12 it is “knocked out”. Is prime number candidate 5 prime number? Let us find out. Look through all previous records in database table for 2==ForwardX. Database table contains 2 records and no records match query 2==ForwardX. 5 is therefore prime number. We know that when x=12 prime number candidate is 2*12+1=25 and cannot be prime number. Add prime number candidate 5 to database table PrimeNumber=5, ForwardX=12. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=4. Id=3, PrimeNumber=5, ForwardX=12. Let x=3. Prime number candidate that corresponds to x=3 is 2*3+1=7. And forwardx is (7*7 -1)/2=24 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=24 it is “knocked out”. Is prime number candidate 7 prime number? Let us find out. Look through all previous records in database table for 3==ForwardX. Database table contains 3 records and no records match query 3==ForwardX. 7 is therefore prime number. We know that when x=24 prime number candidate is 2*24+1=49 and cannot be prime number. Add prime number candidate 7 to database table PrimeNumber=7, ForwardX=24. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=4. Id=3, PrimeNumber=5, ForwardX=12. Id=3, PrimeNumber=7, ForwardX=24. Let x=4. Prime number candidate that corresponds to x=4 is 2*4+1=9. And forwardx is (9*9 -1)/2=40 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=40 it is “knocked out”. Is prime number candidate 9 prime number? Let us find out. Look through all previous records in database table for 4==ForwardX. Database table contains 4 records and one record match query 4==ForwardX. 9 is therefore not prime number. It is “knocked out”. For future queries edit record so that ForwardX=PrimeNumber+ForwardX. And save to database. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=7. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Let x=5. Prime number candidate that corresponds to x=5 is 2*5+1=11. And forwardx is (11*11 -1)/2=60 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=60 it is “knocked out”. Is prime number candidate 11 prime number? Let us find out. Look through all previous records in database table for 5==ForwardX. Database table contains 4 records and no records match query 5==ForwardX. 11 is therefore prime number. We know that when x=60 prime number candidate is 2*60+1=121 and cannot be prime number. Add prime number candidate 11 to database table PrimeNumber=11, ForwardX=60. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=7. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Id=5, PrimeNumber=11, ForwardX=60. Let x=6. Prime number candidate that corresponds to x=6 is 2*6+1=13. And forwardx is (13*13 -1)/2=84 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=84 it is “knocked out”. Is prime number candidate 13 prime number? Let us find out. Look through all previous records in database table for 6==ForwardX. Database table contains 5 records and no records match query 6==ForwardX. 13 is therefore prime number. We know that when x=84 prime number candidate is 2*84+1=169 and cannot be prime number. Add prime number candidate 13 to database table PrimeNumber=13, ForwardX=84. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=7. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Id=5, PrimeNumber=11, ForwardX=60. Id=6, PrimeNumber=13, ForwardX=84. Let x=7. Prime number candidate that corresponds to x=7 is 2*7+1=15. And forwardx is (15*15 -1)/2=224 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=224 it is “knocked out”. Is prime number candidate 15 prime number? Let us find out. Look through all previous records in database table for 7==ForwardX. Database table contains 6 records and one record match query 7==ForwardX. 15 is therefore not prime number. It is “knocked out”. For future queries edit record so that ForwardX=PrimeNumber+ForwardX. And save to database. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=10. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Id=5, PrimeNumber=11, ForwardX=60. Id=6, PrimeNumber=13, ForwardX=84. Let x=8. Prime number candidate that corresponds to x=8 is 2*8+1=17. And forwardx is (17*17 -1)/2=144 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=144 it is “knocked out”. Is prime number candidate 17 prime number? Let us find out. Look through all previous records in database table for 8==ForwardX. Database table contains 6 records and no records match query 8==ForwardX. 17 is therefore prime number. We know that when x=144 prime number candidate is 2*144+1=289 and cannot be prime number. Add prime number candidate 17 to database table PrimeNumber=17, ForwardX=144. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=10. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Id=5, PrimeNumber=11, ForwardX=60. Id=6, PrimeNumber=13, ForwardX=84. Id=7, PrimeNumber=17, ForwardX=144. Let x=9. Prime number candidate that corresponds to x=9 is 2*9+1=19. And forwardx is (19*19 -1)/2=180 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=180 it is “knocked out”. Is prime number candidate 19 prime number? Let us find out. Look through all previous records in database table for 9==ForwardX. Database table contains 7 records and no records match query 9==ForwardX. 19 is therefore prime number. We know that when x=180 prime number candidate is 2*180+1=361 and cannot be prime number. Add prime number candidate 19 to database table PrimeNumber=10, ForwardX=180. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=10. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Id=5, PrimeNumber=11, ForwardX=60. Id=6, PrimeNumber=13, ForwardX=84. Id=7, PrimeNumber=17, ForwardX=144. Id=8, PrimeNumber=19, ForwardX=180. Let x=10. Prime number candidate that corresponds to x=10 is 2*10+1=21. And forwardx is (21*21 -1)/2=220 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=220 it is “knocked out”. Is prime number candidate 21 prime number? Let us find out. Look through all previous records in database table for 10==ForwardX. Database table contains 8 records and one record match query 10==ForwardX. 21 is therefore not prime number. It is “knocked out”. For future queries edit record so that ForwardX=PrimeNumber+ForwardX. And save to database. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=13. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Id=5, PrimeNumber=11, ForwardX=60. Id=6, PrimeNumber=13, ForwardX=84. Id=7, PrimeNumber=17, ForwardX=144. Id=8, PrimeNumber=19, ForwardX=180. And so on... Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=13. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Id=5, PrimeNumber=11, ForwardX=60. Id=6, PrimeNumber=13, ForwardX=84. Id=7, PrimeNumber=17, ForwardX=144. Id=8, PrimeNumber=19, ForwardX=180. Id=9, PrimeNumber=23, ForwardX=264. Id=1, PrimeNumber=2, ForwardX=0. Id=2, PrimeNumber=3, ForwardX=13. Id=3, PrimeNumber=5, ForwardX=12. Id=4, PrimeNumber=7, ForwardX=24. Id=5, PrimeNumber=11, ForwardX=60. Id=6, PrimeNumber=13, ForwardX=84. Id=7, PrimeNumber=17, ForwardX=144. Id=8, PrimeNumber=19, ForwardX=180. Id=9, PrimeNumber=23, ForwardX=264. Id=10, PrimeNumber=29, ForwardX=420. TimoEratosthenes algorithm is the new way using System; using System.Collections.Generic; using System.Linq; namespace TimoEratosthenesConsoleApp { internal class Program { static void Main(string[] args) { int id = 1; int primeNumberCandidate = 2; int x = 0; List primesList = new List { new Prime { Id = id++, PrimeNumber = primeNumberCandidate, ForwardX = x } }; //special case int counter = 0; while (true) { x++; bool isPrimeNumber = true; List forwardXPrimesList = primesList.Where(p => p.ForwardX == x).ToList(); foreach (Prime prime in forwardXPrimesList) { Prime existingPrime = primesList.FirstOrDefault(p => p.Id == prime.Id); if (existingPrime != null) { existingPrime.ForwardX = existingPrime.PrimeNumber + existingPrime.ForwardX; } isPrimeNumber = false; } if (!isPrimeNumber) { continue; } primeNumberCandidate = 2 * x + 1; int forwardX = (primeNumberCandidate * primeNumberCandidate - 1) / 2; primesList.Add( new Prime { Id = id++, PrimeNumber = primeNumberCandidate, ForwardX = forwardX } ); #region show Console.Clear(); foreach (var prime in primesList) { Console.WriteLine( prime ); } Console.ReadKey(); #endregion show counter++; if (counter % 1000 == 0) { Console.Clear(); Console.Write($"Prime number is {primeNumberCandidate}. Number of primenumbers is {counter}."); } } } } public class Prime { public int Id { get; set; } public int PrimeNumber { get; set; } public int ForwardX { get; set; } public override string ToString() { return \$"id={Id} primenumber={PrimeNumber} forwardx={ForwardX}"; } } } Conclusion A new algorithm was introduced by Timo Kinnunen in this paper and explained to a degree so that reader can themselves reproduce and use it. The numbers have it! Starting with prime number 3 and all prime numbers are revealed! Eratosthenes sieve uses division and TimoEratosthenes algorithm not. Saving data as strings in database table or collection makes it possible to produce big prime numbers. The limitation lies often in the chosen datatype i.e. int, uint, long, BigInteger and so on. These limitations are overridden using strings. My hope is that next biggest prime number uses TimoEratosthenes algorithm and that mathematicians can find this algorithm useful to explain prime numbers. Today it is a jungle. Is there hyper-computer somewhere with free time window to implement this algorithm? That’s all folks! Thank you for reading.   2022-01-17, 18:27   #9
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

124078 Posts Quote:
 Originally Posted by TimoKinnunen Eratosthenes sieve uses division [......] Thank you for reading.
It does? Where? When I teach it to children, I don't do any division.

Also, next time you post code use
Code:
 tags   2022-01-17, 23:11   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×7×283 Posts Quote:
 Originally Posted by TimoKinnunen Hunting prime numbers with TimoEratosthenes algorithm Inventor of algorithm and author: Timo Kinnunen born 06/30/1956. ...
I am aware of a lot of smart people that would stop reading after the first line here, above.

Reason: vanity self-naming usually correlates with lack of substance.

In fact, this old golden rule has not failed us here, today.   2022-01-18, 15:20   #11
jwaltos

32×7×53 Posts Quote:
 Originally Posted by Batalov I am aware of a lot of smart people that would stop reading after the first line here, above. Reason: vanity self-naming usually correlates with lack of substance. In fact, this old golden rule has not failed us here, today.
William Gosset..circumstances were different though.

If the original poster reads and appreciates "EWD1036.PDF" on this site: https://www.cs.utexas.edu/users/EWD/index10xx.html
(as a start) then perhaps some better questions may occur to this person.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Hugo1177 Miscellaneous Math 5 2021-02-11 07:40 VicDiesel Programming 12 2017-04-20 21:16 Arxenar Miscellaneous Math 38 2013-06-28 23:26 Citrix Lounge 5 2010-04-05 21:34 Unregistered Miscellaneous Math 8 2008-11-09 07:45

All times are UTC. The time now is 22:16.

Mon Aug 15 22:16:27 UTC 2022 up 39 days, 17:03, 1 user, load averages: 1.15, 1.13, 1.11