



Programming & Packaging A place to discuss programming and packaging. 
14th March 2017, 06:13 AM

Registered User


Join Date: Jun 2013
Location: USA
Posts: 357


Programming Challenge  list prime numbers
Haven't seen one of these programming challenges in a while, so I thought I'd throw one out. Nothing esoteric, just list the prime numbers up to a(n) (arbitrary) point.
Here is one way to do it in python:
Code:
p = [2,3]
x = 5
counter = 1
k=[]
while counter < 10000:
for i in p:
y = x%i
k.append(y)
if 0 not in k:
p.append(x)
k = []
x += 2
counter += 1
print(p)
__________________
Mind the gap.

14th March 2017, 09:47 AM

Registered User


Join Date: Dec 2012
Location: santa barbara, CA
Posts: 391


Re: Programming Challenge  list prime numbers
Just shot this in 10 mins, the first 3 give me zero calcs, due to the bitshifting I use to divide vy 2, which is to granular initially.
Code:
#include <stdio.h>
int main(int argc,char *argv[])
{
register int i=3, c, d, limit, modulo;
long int calculations,total_calculations=0; /* EDITted to be long int */
limit=abs(atoi(argv[1]));
printf("Calculating primes up to: %lu\n",limit);
for (i=3; i< limit; i+=2)
{
d=i>>2;
modulo=1;
calculations=0;
for (c=2;(c<=d) && (modulo > 0);c++)
{
modulo=i%c;
calculations++;
total_calculations++;
}
if (modulo)
{
printf("%lu is prime : calculations: %lu  total calcs: %lu\n", i,calculations,total_calculations);
}
}
}
after some high number runs, I changed the int declaration, to long int, then the total works.
Code:
time ./primes 1000000 > log
real 0m39.440s
user 0m39.275s
sys 0m0.025s
999983 is prime : calculations: 249994  total calcs: 9404063385
so, to get all first 1,000,000 prime numbers, it took my proggy 9404063385 iterations. (9.4 billion)
http://www.servermasters.com/stuff/log.txt.gz
will make some changes to avoid the 5's hehe, forgot about them.
of course this is for singlecore running. I will make one for a 4core cpu, where we just do the 1's 3's 7's and 9's in parallel. hehe, fun fun
Code:
on an old AMD 5300 CPU running the singlecore proggy:
time ./primes 10000000 > 10mill.log.txt
real 56m16.989s
user 55m49.171s
sys 0m2.156s
tail 1 10mill.log.txt
9999991 is prime : calculations: 2499996  total calcs: 801205883487
[bobx@nova test]$ wc l 10mill.log.txt
664580 10mill.log.txt
Here is a revised version, quicker too, since I figured out all dividers of odd numbers are always odd.
Code:
#include <stdio.h>
int main(int argc,char *argv[])
{
register int i=3, c, d, limit, modulo,divider_found;
long int primes_found=0,calculations,total_calculations=0;
limit=abs(atoi(argv[1]));
printf("Calculating primes up to: %lu\n",limit);
for (i=3; i< limit; i+=2)
{
d=i>>2;
modulo=1;
calculations=0;
for (c=3;(c<=d) && (modulo > 0);c+=2)
{
modulo=i%c;
divider_found=c;
calculations++;
total_calculations++;
}
if (modulo)
{
primes_found++;
printf("%lu is prime : calculations: %lu  total calcs: %lu  primes found: %lu\n", i,calculations,total_calculations,primes_found);
}
else
{
printf("Divider found for: %lu > %lu\n", i, divider_found);
}
}
}
Code:
time ./primes 1000000 > 1million_v3.log.txt
real 0m20.020s
user 0m19.862s
sys 0m0.043s
[bobx@nova test]$ tail 20 1million_v3.log.txt
999961 is prime : calculations: 124994  total calcs: 4701762062  primes found: 78496
Divider found for: 999963 > 3
Divider found for: 999965 > 5
Divider found for: 999967 > 31
Divider found for: 999969 > 3
Divider found for: 999971 > 7
Divider found for: 999973 > 13
Divider found for: 999975 > 3
Divider found for: 999977 > 11
999979 is prime : calculations: 124996  total calcs: 4701887092  primes found: 78497
Divider found for: 999981 > 3
999983 is prime : calculations: 124997  total calcs: 4702012090  primes found: 78498
Divider found for: 999985 > 5
Divider found for: 999987 > 3
Divider found for: 999989 > 19
Divider found for: 999991 > 17
Divider found for: 999993 > 3
Divider found for: 999995 > 5
Divider found for: 999997 > 757
Divider found for: 999999 > 3
So, half the number of iterations as before, including much bigger log, but about 1/2 of the CPU time.
Interestingly:
grep Divider 1million_v3.log.txt  cut f6 d' '  sort rn  more
997
991
.
.
.
The max divider found for up to 1,000,000 is almost exactly 1000 times smaller. That's gotta be of significance, and I will see if I put some contraints on the divider search loop, and test/compare it up to waz00 numbers, to see if it works.
Last edited by bobx001; 14th March 2017 at 12:16 PM.

16th March 2017, 04:52 AM

Registered User


Join Date: Nov 2006
Location: Detroit
Posts: 6,587


Re: Programming Challenge  list prime numbers
Oneliner using Octave to list the first 10,000 primes:
Code:
$ octave eval 'printf("%d ", list_primes(10000))'
__________________
OS: Fedora 25 x86_64  Machine: HP Pavilion a6130n  CPU: AMD 64 X2 DualCore 5000+ 2.6GHz  RAM: 7GB PC5300 DDR2  Disk: 400GB SATA  Video: ATI Radeon HD 4350 512MB  Sound: Realtek ALC888S  Ethernet: Realtek RTL8201N

16th March 2017, 07:18 AM

Registered User


Join Date: Jun 2013
Location: USA
Posts: 357


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by RupertPupkin
Oneliner using Octave to list the first 10,000 primes:
Code:
$ octave eval 'printf("%d ", list_primes(10000))'

Very impressive. I was going to install this mysterious Octave, but, at least on the machine I am currently in front of, it looks like a 237 MB installation with the necessary dependencies yet to be installed. Maybe in future...
__________________
Mind the gap.
Last edited by hiGuys; 16th March 2017 at 07:26 AM.
Reason: clarification

16th March 2017, 07:25 AM

Registered User


Join Date: Jun 2013
Location: USA
Posts: 357


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by bobx001
Code:
time ./primes 1000000 > 1million_v3.log.txt
real 0m20.020s
user 0m19.862s
sys 0m0.043s
[bobx@nova test]$ tail 20 1million_v3.log.txt
999961 is prime : calculations: 124994  total calcs: 4701762062  primes found: 78496
Divider found for: 999963 > 3
Divider found for: 999965 > 5
Divider found for: 999967 > 31
Divider found for: 999969 > 3
Divider found for: 999971 > 7
Divider found for: 999973 > 13
Divider found for: 999975 > 3
Divider found for: 999977 > 11
999979 is prime : calculations: 124996  total calcs: 4701887092  primes found: 78497
Divider found for: 999981 > 3
999983 is prime : calculations: 124997  total calcs: 4702012090  primes found: 78498
Divider found for: 999985 > 5
Divider found for: 999987 > 3
Divider found for: 999989 > 19
Divider found for: 999991 > 17
Divider found for: 999993 > 3
Divider found for: 999995 > 5
Divider found for: 999997 > 757
Divider found for: 999999 > 3
So, half the number of iterations as before, including much bigger log, but about 1/2 of the CPU time.
Interestingly:
grep Divider 1million_v3.log.txt  cut f6 d' '  sort rn  more
997
991
.
.
.
The max divider found for up to 1,000,000 is almost exactly 1000 times smaller. That's gotta be of significance, and I will see if I put some contraints on the divider search loop, and test/compare it up to waz00 numbers, to see if it works.

I like showing the divisors. That could be useful depending what one wanted to do with primes.
__________________
Mind the gap.

16th March 2017, 01:19 PM

Registered User


Join Date: Oct 2010
Location: Canberra
Posts: 2,575


Re: Programming Challenge  list prime numbers
Hmmm, a one line call to a function called list_primes is hardly in the spirit of a programming challenge thread.
As for a solution involving division operators when the ancient Greeks had a much more efficient solution .
Might I suggest doing just a smidgin of research before launching into writing code.
Solutions to this problem get much more interesting when you try to make the best use of the available cores and keep as much as possible in the local cache.
__________________
Has anyone seriously considered that it might be turtles all the way down?
That's very old fashioned thinking.
The current model is that it's holographic nested virtualities of turtles, all the way down.

16th March 2017, 04:10 PM

Registered User


Join Date: Jun 2013
Location: USA
Posts: 357


Re: Programming Challenge  list prime numbers
It's interesting you mention research first, because part of my thinking in this was to independently come up with a solution without reference to preexisting knowledge of the solutions. Yes, there is a huge database of research into primes, but my personal interest was in creating home brew solutions, not discovering or optimizing the solution to millennia of thinking on a chat forum. But since you mention the Greeks, I look forward to seeing what they had to say on the matter.
__________________
Mind the gap.

16th March 2017, 05:38 PM

Registered User


Join Date: Dec 2012
Location: santa barbara, CA
Posts: 391


Re: Programming Challenge  list prime numbers
I just like to walk the walk, and come up with my own conclusions. It's the fun of programming that keeps me alive. Besides number theorems and their logic implementations are more expensive programatically than simple iteration most of the times.

16th March 2017, 07:05 PM

Registered User


Join Date: Jun 2005
Location: Montreal, Que, Canada
Posts: 4,102


Re: Programming Challenge  list prime numbers
Is there still a better method? I was thinking of looking at the prime factors of the integer immediately bow the prime and start by manipulating those integers by adding one to each, one at a time. I think we know enough info to avoid unnecessary recalcs

16th March 2017, 11:11 PM

Registered User


Join Date: Oct 2010
Location: Canberra
Posts: 2,575


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by bobx001
I just like to walk the walk, and come up with my own conclusions. It's the fun of programming that keeps me alive. Besides number theorems and their logic implementations are more expensive programatically than simple iteration most of the times.

You are quite right about keeping it simple. There are some improved variations on the "Sieve of Eratosthenes" but they don't overtake the basic form until you start to get into very large numbers.
The SoE algorithm starts with a bitmap of all the numbers in the desired range and then, using just addition, flags all the multiples of each prime number. An obvious speedup is to skip the even numbers.
Advanced versions subdivide the bitmap into cache sized chunks to avoid slow external memory addressing, and spread the work over all available cores. (These are in addition to the improved algorithms, mentioned above.)
__________________
Has anyone seriously considered that it might be turtles all the way down?
That's very old fashioned thinking.
The current model is that it's holographic nested virtualities of turtles, all the way down.

17th March 2017, 12:06 AM

Registered User


Join Date: Nov 2006
Location: Detroit
Posts: 6,587


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by hiGuys
I was going to install this mysterious Octave, but, ...

I think Octave is definitely worth installing. It's basically a free Matlab clone. But there are alternatives with smaller footprints.
IDL is one such alternative. Here's an IDL oneliner to list the first 10,000 primes (using GDL, a free GNU implementation of IDL, which is in the Fedora repos: dnf install gdl):
Code:
$ gdl q e 'print, primes(10000)'
__________________
OS: Fedora 25 x86_64  Machine: HP Pavilion a6130n  CPU: AMD 64 X2 DualCore 5000+ 2.6GHz  RAM: 7GB PC5300 DDR2  Disk: 400GB SATA  Video: ATI Radeon HD 4350 512MB  Sound: Realtek ALC888S  Ethernet: Realtek RTL8201N

17th March 2017, 01:18 AM

Registered User


Join Date: Nov 2006
Location: Detroit
Posts: 6,587


Re: Programming Challenge  list prime numbers
Here's a way in Java to get the first N > 1 primes:
Code:
public class getPrimes {
public static void main(String[] args) {
int N = Integer.parseInt(args[0]), p = 3, counter = 1;
System.out.print("2");
while (counter < N) {
if (isPrime(p)) {
System.out.print(", " + p);
counter++;
}
p += 2;
}
System.out.println("");
}
private static boolean isPrime(int odd) {
boolean result = true;
if (odd > 3) {
if (odd%3 == 0) {
result = false;
} else {
for (int i = 5; i*i <= odd; i += 6) {
if (odd%i == 0  odd%(i+2) == 0) {
result = false;
break;
}
}
}
}
return result;
}
}
Compile and run:
Code:
$ javac getPrimes.java
$ java getPrimes 10
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
$ java getPrimes 100
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541
Takes just under 5 seconds to get the first 1 million primes, and just over 2 minutes to get the first 10 million primes:
Code:
$ time java getPrimes 1000000 > primes.log
real 0m4.912s
user 0m4.141s
sys 0m0.859s
$ time java getPrimes 10000000 > primes.log
real 2m8.225s
user 1m57.553s
sys 0m8.833s
__________________
OS: Fedora 25 x86_64  Machine: HP Pavilion a6130n  CPU: AMD 64 X2 DualCore 5000+ 2.6GHz  RAM: 7GB PC5300 DDR2  Disk: 400GB SATA  Video: ATI Radeon HD 4350 512MB  Sound: Realtek ALC888S  Ethernet: Realtek RTL8201N

17th March 2017, 02:37 AM

Registered User


Join Date: Jun 2005
Location: Montreal, Que, Canada
Posts: 4,102


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by bobx001
Just shot this in 10 mins, the first 3 give me zero calcs, due to the bitshifting I use to divide vy 2, which is to granular initially.
Code:
#include <stdio.h>
int main(int argc,char *argv[])
{
register int i=3, c, d, limit, modulo;
long int calculations,total_calculations=0; /* EDITted to be long int */
limit=abs(atoi(argv[1]));
printf("Calculating primes up to: %lu\n",limit);
for (i=3; i< limit; i+=2)
{
d=i>>2;
modulo=1;
calculations=0;
for (c=2;(c<=d) && (modulo > 0);c++)
{
modulo=i%c;
calculations++;
total_calculations++;
}
if (modulo)
{
printf("%lu is prime : calculations: %lu  total calcs: %lu\n", i,calculations,total_calculations);
}
}
}
after some high number runs, I changed the int declaration, to long int, then the total works.
Code:
time ./primes 1000000 > log
real 0m39.440s
user 0m39.275s
sys 0m0.025s
999983 is prime : calculations: 249994  total calcs: 9404063385
so, to get all first 1,000,000 prime numbers, it took my proggy 9404063385 iterations. (9.4 billion)
http://www.servermasters.com/stuff/log.txt.gz
will make some changes to avoid the 5's hehe, forgot about them.
of course this is for singlecore running. I will make one for a 4core cpu, where we just do the 1's 3's 7's and 9's in parallel. hehe, fun fun
Code:
on an old AMD 5300 CPU running the singlecore proggy:
time ./primes 10000000 > 10mill.log.txt
real 56m16.989s
user 55m49.171s
sys 0m2.156s
tail 1 10mill.log.txt
9999991 is prime : calculations: 2499996  total calcs: 801205883487
[bobx@nova test]$ wc l 10mill.log.txt
664580 10mill.log.txt
Here is a revised version, quicker too, since I figured out all dividers of odd numbers are always odd.
Code:
#include <stdio.h>
int main(int argc,char *argv[])
{
register int i=3, c, d, limit, modulo,divider_found;
long int primes_found=0,calculations,total_calculations=0;
limit=abs(atoi(argv[1]));
printf("Calculating primes up to: %lu\n",limit);
for (i=3; i< limit; i+=2)
{
d=i>>2;
modulo=1;
calculations=0;
for (c=3;(c<=d) && (modulo > 0);c+=2)
{
modulo=i%c;
divider_found=c;
calculations++;
total_calculations++;
}
if (modulo)
{
primes_found++;
printf("%lu is prime : calculations: %lu  total calcs: %lu  primes found: %lu\n", i,calculations,total_calculations,primes_found);
}
else
{
printf("Divider found for: %lu > %lu\n", i, divider_found);
}
}
}
Code:
time ./primes 1000000 > 1million_v3.log.txt
real 0m20.020s
user 0m19.862s
sys 0m0.043s
[bobx@nova test]$ tail 20 1million_v3.log.txt
999961 is prime : calculations: 124994  total calcs: 4701762062  primes found: 78496
Divider found for: 999963 > 3
Divider found for: 999965 > 5
Divider found for: 999967 > 31
Divider found for: 999969 > 3
Divider found for: 999971 > 7
Divider found for: 999973 > 13
Divider found for: 999975 > 3
Divider found for: 999977 > 11
999979 is prime : calculations: 124996  total calcs: 4701887092  primes found: 78497
Divider found for: 999981 > 3
999983 is prime : calculations: 124997  total calcs: 4702012090  primes found: 78498
Divider found for: 999985 > 5
Divider found for: 999987 > 3
Divider found for: 999989 > 19
Divider found for: 999991 > 17
Divider found for: 999993 > 3
Divider found for: 999995 > 5
Divider found for: 999997 > 757
Divider found for: 999999 > 3
So, half the number of iterations as before, including much bigger log, but about 1/2 of the CPU time.
Interestingly:
grep Divider 1million_v3.log.txt  cut f6 d' '  sort rn  more
997
991
.
.
.
The max divider found for up to 1,000,000 is almost exactly 1000 times smaller. That's gotta be of significance, and I will see if I put some contraints on the divider search loop, and test/compare it up to waz00 numbers, to see if it works.

If a number ends in a 5, it is not prime. There was also another rule about the sum of the digits. (Sum of digits divisible by 3) can be factored  not prime

17th March 2017, 04:07 AM

Registered User


Join Date: Oct 2010
Location: Canberra
Posts: 2,575


Re: Programming Challenge  list prime numbers
Here is my simple Sieve of Eratosthenes solution (taken from Wikipedia pseudocode):
Code:
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>
using namespace std;
typedef unsigned long int ul64;
int main(int argc,char *argv[])
{
ul64 limit=abs(atol(argv[1]));
printf("Calculating primes up to: %lu\n",limit);
limit++;
vector<bool> primes(limit, true);
ul64 range = sqrt(limit);
for( ul64 i=2; i<=range; i++)
{
if( primes[i] )
{
ul64 ii = i*i;
ul64 k = ii;
for ( ul64 j=0; k<limit; j++ )
{
primes[k] = false;
k += i;
}
}
}
for(ul64 i=2; i<limit; i++)
{
if( primes[i] ) printf("%lu\n", i );
}
}
~
For comparison, on my machine bobx001's solution takes 46.6 seconds for 1 million.
Code:
[brenton@acer primes]$ time ./primes3 1000000 > primes3.dat
real 0m0.024s
user 0m0.021s
sys 0m0.003s
[brenton@acer primes]$ time ./primes3 1000000000 > primes3.dat
real 0m18.232s
user 0m17.725s
sys 0m0.513s
I did a diff to make sure it got the same results.
__________________
Has anyone seriously considered that it might be turtles all the way down?
That's very old fashioned thinking.
The current model is that it's holographic nested virtualities of turtles, all the way down.
Last edited by ocratato; 17th March 2017 at 12:49 PM.

17th March 2017, 05:24 AM

Registered User


Join Date: Nov 2006
Location: Detroit
Posts: 6,587


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by ocratato
Here is my simple Sieve of Eratosthenes solution (taken from Wikipedia pseudocode):
Code:
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>
using namespace std;
typedef unsigned long int ul32;
int main(int argc,char *argv[])
{
ul32 limit=abs(atoi(argv[1]));
printf("Calculating primes up to: %lu\n",limit);
vector<bool> primes(limit, true);
ul32 range = sqrt(limit);
for( ul32 i=2; i<range; i++)
{
if( primes[i] )
{
ul32 ii = i*i;
ul32 k;
for ( ul32 j=0; (k=ii+j*i)<limit; j++ )
{
primes[k] = false;
}
}
}
for(ul32 i=3; i<limit; i++)
{
if( primes[i] ) printf("%lu\n", i );
}
}
For comparison, on my machine bobx001's solution takes 46.6 seconds for 1 million.

In fact, I just compiled and ran your program, and it doesn't quite do what it says:
Code:
$ ./getPrimes 11
Calculating primes up to: 11
3
5
7
9
So not only is the nonprime number 9 listed, but 11 is missing (so that it's not "up to" 11), and even 2 is missing!
Maybe you should do a little research before writing code, and not blindly copy code from Wikipedia.
Edit: To be fair, bobx001's program also wrongly lists 9 as a prime number and makes the same mistakes that yours does. His program does print out more info (like divisors), though, so the time comparisons are kind of apples to oranges.
__________________
OS: Fedora 25 x86_64  Machine: HP Pavilion a6130n  CPU: AMD 64 X2 DualCore 5000+ 2.6GHz  RAM: 7GB PC5300 DDR2  Disk: 400GB SATA  Video: ATI Radeon HD 4350 512MB  Sound: Realtek ALC888S  Ethernet: Realtek RTL8201N
Last edited by RupertPupkin; 17th March 2017 at 05:51 AM.
Reason: Read the wrong post for bobx001.

Thread Tools 
Search this Thread 


Display Modes 
Linear Mode

Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



Current GMTtime: 14:39 (Thursday, 27072017)







