mersenneforum.org Need an assessment and help regarding prime numbers.
 Register FAQ Search Today's Posts Mark Forums Read

2022-01-05, 13:30   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

22×3×17×31 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 237678 Posts 2000 primes per minute in the lower realms does not sound fast.
2022-01-05, 14:39   #4
axn

Jun 2003

24×7×47 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 14768 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

17C816 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 23·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 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

 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 11:03.

Mon Jan 17 11:03:28 UTC 2022 up 178 days, 5:32, 0 users, load averages: 1.13, 0.97, 0.97