20220105, 13:24  #1 
"Timo Kinnunen"
Jan 2022
Sweden
1_{16} 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<PrimeNumberItem> 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; // } // } // } 
20220105, 13:30  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}×3×17×31 Posts 
Quote:
Your code does what is known as trial factoring, TF for short. It isn't revolutionary. Last fiddled with by retina on 20220105 at 13:32 

20220105, 14:31  #3 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
23767_{8} Posts 
2000 primes per minute in the lower realms does not sound fast.

20220105, 14:39  #4 
Jun 2003
2^{4}×7×47 Posts 

20220105, 14:45  #5 
"Oliver"
Sep 2017
Porta Westfalica, DE
1476_{8} 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<int>(); 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: ; } 
20220105, 18:44  #6  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
17C8_{16} Posts 
Welcome to GIMPS (assuming you're here in good faith).
Quote:
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 20220105 at 18:46 

20220106, 01:23  #7 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
2^{3}·761 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<PrimeNumberItem> 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; } } } 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. Multithreaded Chapel 128.279 msec, ~396. primes/ MICROsecond. The Fortran result 219 msec for up to a billion on Intel Skylake i56500 CPU at 3.2 GHz multithreaded with four cores, corresponds to ~232,180,520 primes/sec. Plus there's an estimated nearfourfold and a neardouble 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 i52500 CPU @ 3.6 GHz (turbo boost for single threaded) Single threaded NIM up to a billion in 0.793 sec, with untested further nearfourfold and twofold 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 20220106 at 01:36 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Congruent prime numbers that preserves the modulo as the largest prime factor of the sum  Hugo1177  Miscellaneous Math  5  20210211 07:40 
What can you do with 2 prime numbers?  VicDiesel  Programming  12  20170420 21:16 
Prime Numbers Or Not  Arxenar  Miscellaneous Math  38  20130628 23:26 
All odd numbers are prime  Citrix  Lounge  5  20100405 21:34 
Prime numbers  Unregistered  Miscellaneous Math  8  20081109 07:45 