



Programming & Packaging A place to discuss programming and packaging. 
18th March 2017, 08:20 PM

Registered User


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


Re: Programming Challenge  list prime numbers
Here's an example in Julia. It only lists all primes up to the number N, so it's comparable to the examples other people here have given. It requires Julia 0.5.0, which is in the F25 repos (dnf install julia).
Save this as getPrimes.jl:
Code:
import Primes
println(primes(2, parse(Int64, ARGS[1])))
Sample output:
Code:
$ julia getPrimes.jl 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]
Takes under 2 seconds to get all primes up to 1 million, and under 40 seconds for up to 1 billion:
Code:
$ time julia getPrimes.jl 1000000 > primes.log
real 0m1.634s
user 0m1.471s
sys 0m0.250s
$ time julia getPrimes.jl 1000000000 > primes.log
real 0m38.366s
user 0m30.577s
sys 0m2.235s
__________________
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

18th March 2017, 08:50 PM

Registered User


Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157


Re: Programming Challenge  list prime numbers
This is in Python 3. Mine is not as performant as the latest examples, but I just thought I would share.
Code:
#!/usr/bin/env python3
import sys
def eratosthenes_sieve(n):
our_list = []
marks = []
for e in range(2, n+1):
our_list.append(e)
marks.append(None)
i = 0
while i < len(our_list) / 2:
if marks[i] is None:
j = 2
while j * our_list[i] <= our_list[1]:
marks[(j*our_list[i])2] = True
j += 1
i += 1
new_list = []
i = 0
while i < len(marks):
if marks[i] is None:
new_list.append(our_list[i])
i += 1
return new_list
if __name__ == '__main__':
print(eratosthenes_sieve(int(sys.argv[1])))
__________________
OS: Arch Linux x86_64
Laptop: Lenovo ThinkPad L440, CPU: Intel Core i7 4702MQ Quad Core 2.20 GHz, Ram: 16GB DDR3, Hard Drive: 500GB, Graphics: Intel 4600 HD, Wireless: Intel 7260AC

19th March 2017, 05:49 AM

Registered User


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


Re: Programming Challenge  list prime numbers
Flounder, I'm surprised you didn't do a Perl example. Here's one that lists all the primes (hit Ctrlc to stop):
Code:
$ perl e '$++;(1 x$_)!~/^1?$^(11+?)\1+$/&&print"$_ "while ++$_'
__________________
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

19th March 2017, 07:47 AM

Registered User


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


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by RupertPupkin
Flounder, I'm surprised you didn't do a Perl example. Here's one that lists all the primes (hit Ctrlc to stop):
Code:
$ perl e '$++;(1 x$_)!~/^1?$^(11+?)\1+$/&&print"$_ "while ++$_'

Sorry, can you post that again  I seem to have just got line noise.
__________________
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.

19th March 2017, 02:47 PM

Registered User


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


Re: Programming Challenge  list prime numbers
This is encouraging.
Prior to splitting the processing across threads I modified the algorithm to use a vector of bitset rather than a vector of bool. The bitsets are 200K bits and will be the pages that are to be processed by the threads.
The good news is that despite the additional overhead of handling pages the result is a second faster (13 secs for a billion).
About 3 seconds of the total is printing the results, so with 4 cores I hope to get under 6 seconds for the total.
__________________
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.

19th March 2017, 04:11 PM

Registered User


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


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by ocratato
This is encouraging.
Prior to splitting the processing across threads I modified the algorithm to use a vector of bitset rather than a vector of bool. The bitsets are 200K bits and will be the pages that are to be processed by the threads.
The good news is that despite the additional overhead of handling pages the result is a second faster (13 secs for a billion).
About 3 seconds of the total is printing the results, so with 4 cores I hope to get under 6 seconds for the total.

Awesome. I'll get back on the boat on Tue. On another project atm.
Question, did you use byte alignment (char array) for the bit pools or long ints ?

19th March 2017, 05:54 PM

Registered User


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


Re: Programming Challenge  list prime numbers
Here's an example in Scheme to get the primes up to N>=1, using the Guile interpreter (dnf install guile).
Save this as getPrimes.scm:
Code:
(define (primes n)
(let ((bits (makevector (+ n 1) #t)))
(let loop ((p 2) (ps '()))
(cond ((< n p) (reverse ps))
((vectorref bits p)
(do ((i (+ p p) (+ i p))) ((< n i))
(vectorset! bits i #f))
(loop (+ p 1) (cons p ps)))
(else (loop (+ p 1) ps))))))
(define (main args) (display (primes (string>number (cadr args))))(newline))
Sample output:
Code:
$ guile noautocompile e main s getPrimes.scm 101
(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)
__________________
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

20th March 2017, 05:38 AM

Registered User


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


Re: Programming Challenge  list prime numbers
Here is my multithreaded C++ version:
Code:
// a multithreaded seive of Eratosthenes
//
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <thread>
#include <cmath>
using namespace std;
typedef unsigned long int ul64;
//
// Use a bitset to hold the flags indicating if we
// have found a prime.
// The size should be small enough to fit in a CPU cache (32KB)
// given that the bitset stores 8 bits per byte.
const ul64 BITSETSZ = 200000;
typedef bitset<BITSETSZ> Bits;
// Ideally this would be determined at run time.
const int NumThreads = 4;
// 
// Provide our own alternative to printf that is dedicated to
// printing integers and buffers its results to reduce I/O overhead.
//
inline void print_int(ul64 val)
{
static char outbuf[4096];
static int p = 0;
char chars[16];
int digits = 0;
//
// Pass zero to flush the buffer.
if ( val == 0 )
{
fwrite(outbuf, 1, p, stdout );
p = 0;
return;
}
do
{
chars[digits++] = ((val % 10) + 0x30);
val /= 10;
} while (val && digits < 16);
while (digits>0)
{
outbuf[p++] = chars[digits];
}
outbuf[p++] = '\n';
if ( p > 4080 )
{
fwrite(outbuf, 1, p, stdout );
p = 0;
}
}
// 
//
// Print the prime numbers.
//
void print_results( vector<Bits> & primes, ul64 limit )
{
ul64 numPages = primes.size();
Bits & primeSetZero = primes[0];
//
// If there is only one page then it will be starting at 2
// and ending at limit.
// Otherwise the first page starts a 2 and the last page
// ends at limit. All other pages print the entire range.
//
if ( numPages == 1 )
{
for( ul64 i=2; i<=limit; i++ )
{
if( primeSetZero[i] ) print_int( i );
}
}
else
{
for(ul64 i=2; i<BITSETSZ; i++)
{
if( primeSetZero[i] ) print_int( i );
}
for( ul64 p=1; p<numPages1; p++ )
{
ul64 x = p * BITSETSZ;
Bits & primeSet = primes[p];
for(ul64 i=0; i<BITSETSZ; i++)
{
if( primeSet[i] ) print_int( x + i );
}
}
ul64 x = (numPages1) * BITSETSZ;
for( ul64 i=0; (x+i)<=limit; i++ )
{
if( primes[numPages1][i] ) print_int( x+i );
}
}
print_int(0); // flush the buffer
}
// 
void cull_pages( vector<Bits> & primes, int thread )
{
//
// cull out the multiples of each prime on each page
ul64 numPages = primes.size();
Bits & primeSetZero = primes[0];
for( ul64 p=thread; p<numPages; p += NumThreads )
{
Bits & primeSet = primes[p];
// loop over the primes in the first page
for( ul64 i=2; i<BITSETSZ; i++)
{
if( primeSetZero[i] )
{
// calculate the offset of this prime on this page
ul64 k = (p * BITSETSZ) % i;
if ( k ) k = i  k;
//
// cull out the multiples
while( k < BITSETSZ )
{
primeSet[k] = false;
k += i;
}
}
}
}
}
// 
int main(int argc,char *argv[])
{
ul64 limit=atoll(argv[1]);
printf("Calculating primes up to: %lu\n",limit);
//
// make sure we include the end in our seive
limit++;
//
// The largest factor of limit is sqrt(limit)
ul64 range = sqrt(limit);
if ( BITSETSZ < range )
{
//
// Limit ourselves to 40 billion
ul64 n = BITSETSZ*BITSETSZ;
printf( "max range for program is %lu\n", n );
return 1;
}
//
// Now we need enough bitsets to hold the entire range
// (Later  odd numbers only).
vector< Bits > primes( limit / BITSETSZ +1);
//
// initialise to set;
for( auto &b : primes) b.set();
//
// first we calc the primes for the first page
Bits & primeSetZero = primes[0];
for( ul64 i=2; i<BITSETSZ; i++)
{
if( primeSetZero[i] )
{
ul64 k = i*i;
while( k < BITSETSZ )
{
primeSetZero[k] = false;
k += i;
}
}
}
//
// Then we cull the remaining pages.
// start the threads
std::thread threads[NumThreads];
for (int t=0; t<NumThreads; t++ )
{
// std::ref is our promise that primes will hang around
// until the thread finishes.
threads[t] = std::thread( cull_pages, std::ref(primes), t+1 );
}
//
// Wait until they are done
for (int t=0; t<NumThreads; t++ )
{
threads[t].join();
}
print_results( primes, limit );
return 0;
}
Code:
[brenton@acer primes]$ g++ Ofast std=c++11 primes4.cpp o primes4 lpthread
[brenton@acer primes]$ time ./primes4 1000000000 > primes4.dat
real 0m8.233s
user 0m17.938s
sys 0m0.708s
__________________
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; 21st March 2017 at 01:10 AM.

20th March 2017, 09:27 AM

Registered User


Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by RupertPupkin
Flounder, I'm surprised you didn't do a Perl example. Here's one that lists all the primes (hit Ctrlc to stop):
Code:
$ perl e '$++;(1 x$_)!~/^1?$^(11+?)\1+$/&&print"$_ "while ++$_'

I actually don't know Perl. I've thought about learning it at some point, but right now I'm trying to focus on getting stuff done rather than learning more languages.
Here's another example in Rust that I did when starting off CIS198.
eratosthenes.rs
Code:
use std::env;
/// Find all prime numbers less than `n`.
/// For example, `sieve(7)` should return `[2, 3, 5]`
pub fn sieve(n: u32) > Vec<u32> {
let mut ns: Vec<u32> = Vec::new();
let mut marks: Vec<bool> = Vec::new();
let mut primes: Vec<u32> = Vec::new();
let mut i = 2;
// Populate the vector with numbers 2..n
while i <= n {
ns.push(i);
marks.push(false);
i += 1;
}
// mark all nonprime numbers
let mut i: usize = 0;
while i < ns.len() {
if marks[i] == false {
let step = ns[i] as usize;
let mut j = i + step;
primes.push(step as u32);
while j < marks.len() {
marks[j] = true;
j += step;
}
}
i += 1;
}
// Should be only primes now
primes
}
fn main() {
let args: Vec<_> = env::args().collect();
if args.len() > 1 {
let n: u32 = args[1].parse().unwrap();
let primes = sieve(n);
for x in primes {
print!("{} ", x);
}
print!("\n");
}
}
Compile with:
Code:
rustc eratosthenes.rs
You can get rustc either through rustup or the repos.
Writing a Haskell example is going to be a bit tricky, but I think I can get similar performance to Python with it.
__________________
OS: Arch Linux x86_64
Laptop: Lenovo ThinkPad L440, CPU: Intel Core i7 4702MQ Quad Core 2.20 GHz, Ram: 16GB DDR3, Hard Drive: 500GB, Graphics: Intel 4600 HD, Wireless: Intel 7260AC

20th March 2017, 10:21 PM

Registered User


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


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by Flounder
I actually don't know Perl.

Oh yeah, that's right  you're the Python guy. I got you mixed up with ah7013, the Perl guy.
__________________
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

21st March 2017, 12:15 AM

Registered User


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


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by ocratato
Here is my multithreaded C++ version:
Code:
// a multithreaded seive of Eratosthenes
//
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <thread>
#include <cmath>
using namespace std;
typedef unsigned long int ul64;
//
// Use a bitset to hold the flags indicating if we
// have found a prime.
// The size should be small enough to fit in a CPU cache (32KB)
// given that the bitset stores 8 bits per byte.
const ul64 BITSETSZ = 200000;
typedef bitset<BITSETSZ> Bits;
// Ideally this would be determined at run time.
const int NumThreads = 4;
// 
// Provide our own alternative to printf that is dedicated to
// printing integers and buffers its results to reduce I/O overhead.
//
inline void print_int(ul64 val)
{
static char outbuf[4096];
static int p = 0;
char chars[16];
int digits = 0;
//
// Pass zero to flush the buffer.
if ( val == 0 )
{
fwrite(outbuf, 1, p, stdout );
p = 0;
return;
}
do
{
chars[digits++] = ((val % 10) + 0x30);
val /= 10;
} while (val && digits < 16);
while (digits>0)
{
outbuf[p++] = chars[digits];
}
outbuf[p++] = '\n';
if ( p > 4080 )
{
fwrite(outbuf, 1, p, stdout );
p = 0;
}
}
// 
//
// Print the prime numbers.
//
void print_results( vector<Bits> & primes, ul64 limit )
{
ul64 numPages = primes.size();
Bits & primeSetZero = primes[0];
//
// If there is only one page then it will be starting at 2
// and ending at limit.
// Otherwise the first page starts a 2 and the last page
// ends at limit. All other pages print the entire range.
//
if ( numPages == 1 )
{
for( ul64 i=2; i<=limit; i++ )
{
if( primeSetZero[i] ) print_int( i );
}
}
else
{
for(ul64 i=2; i<BITSETSZ; i++)
{
if( primeSetZero[i] ) print_int( i );
}
for( ul64 p=1; p<numPages1; p++ )
{
ul64 x = p * BITSETSZ;
Bits & primeSet = primes[p];
for(ul64 i=0; i<BITSETSZ; i++)
{
if( primeSet[i] ) print_int( x + i );
}
}
ul64 x = numPages * BITSETSZ;
for( ul64 i=0; (x+i)<=limit; i++ )
{
if( primes[numPages1][i] ) print_int( x+i );
}
}
print_int(0); // flush the buffer
}
// 
void cull_pages( vector<Bits> & primes, int thread )
{
//
// cull out the multiples of each prime on each page
ul64 numPages = primes.size();
Bits & primeSetZero = primes[0];
for( ul64 p=thread; p<numPages; p += NumThreads )
{
Bits & primeSet = primes[p];
// loop over the primes in the first page
for( ul64 i=2; i<BITSETSZ; i++)
{
if( primeSetZero[i] )
{
// calculate the offset of this prime on this page
ul64 k = (p * BITSETSZ) % i;
if ( k ) k = i  k;
//
// cull out the multiples
while( k < BITSETSZ )
{
primeSet[k] = false;
k += i;
}
}
}
}
}
// 
int main(int argc,char *argv[])
{
ul64 limit=atoll(argv[1]);
printf("Calculating primes up to: %lu\n",limit);
//
// make sure we include the end in our seive
limit++;
//
// The largest factor of limit is sqrt(limit)
ul64 range = sqrt(limit);
if ( BITSETSZ < range )
{
//
// Limit ourselves to 40 billion
ul64 n = BITSETSZ*BITSETSZ;
printf( "max range for program is %lu\n", n );
return 1;
}
//
// Now we need enough bitsets to hold the entire range
// (Later  odd numbers only).
vector< Bits > primes( limit / BITSETSZ +1);
//
// initialise to set;
for( auto &b : primes) b.set();
//
// first we calc the primes for the first page
Bits & primeSetZero = primes[0];
for( ul64 i=2; i<BITSETSZ; i++)
{
if( primeSetZero[i] )
{
ul64 k = i*i;
while( k < BITSETSZ )
{
primeSetZero[k] = false;
k += i;
}
}
}
//
// Then we cull the remaining pages.
// start the threads
std::thread threads[NumThreads];
for (int t=0; t<NumThreads; t++ )
{
// std::ref is our promise that primes will hang around
// until the thread finishes.
threads[t] = std::thread( cull_pages, std::ref(primes), t+1 );
}
//
// Wait until they are done
for (int t=0; t<NumThreads; t++ )
{
threads[t].join();
}
print_results( primes, limit );
return 0;
}
Code:
[brenton@acer primes]$ g++ Ofast std=c++11 primes4.cpp o primes4 lpthread
[brenton@acer primes]$ time ./primes4 1000000000 > primes4.dat
real 0m8.233s
user 0m17.938s
sys 0m0.708s

Hmm, it looks like your program has a serious error. For example, the 20,000th prime number is 224737, so your program should find it if you pass it the number 224738 on the command line. But it doesn't:
Code:
$ ./getPrimes2 224738  grep 224737
$
In fact, your program doesn't show 2016 of the first 20,000 primes:
Code:
$ ./getPrimes2 224738  tail n +2  wc l
17984
That number should be 20000, not 17984. So it's missing over 10% of the first 20,000 primes!
Look at the last 10 primes before 224738 that it finds:
Code:
$ ./getPrimes2 224738  tail
199873
199877
199889
199909
199921
199931
199933
199961
199967
199999
That list should look like this:
Code:
224629
224633
224669
224677
224683
224699
224711
224717
224729
224737
Similar errors occur for larger numbers of primes. So your program is fast, but just not accurate.
__________________
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

21st March 2017, 01:56 AM

Registered User


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


Re: Programming Challenge  list prime numbers
@RupertPupkin Thanks for spotting that. My tests happened to be multiples of the page size so they didn't test the printing of the last page of the results. A rather large offbyone error  now fixed in the original post.
I am using an Intel i5 processor: i52430M CPU @ 2.40GHz
This has two cores with "hyperthreading". This has some interesting consequences. I created three versions of my program with 1, 2 and 4 threads and got the following times:
Code:
[brenton@acer primes]$ time ./primes41 1000000000 > primes4.dat
real 0m12.807s
user 0m12.315s
sys 0m0.495s
[brenton@acer primes]$ time ./primes42 1000000000 > primes4.dat
real 0m8.871s
user 0m12.899s
sys 0m0.503s
[brenton@acer primes]$ time ./primes44 1000000000 > primes4.dat
real 0m8.025s
user 0m17.899s
sys 0m0.503s
Since about 20% of the total processing is spent in the single threaded print_results routine the drop in real time for the two thread version looks to be near optimum. However, when going to 4 threads there is a jump of 5 seconds in the user time and only a very minor improvement in the real time. My conclusion is that "hyperthreading" doesn't really live up to its name.
Further Improvements
If I come back to this program, there are some more improvements that could be made:  Get rid of the even numbers. This will speed it up and also double the size of the sieve that can be handled.
 Have the threads work on contiguous blocks of pages rather than the interleaved approach currently used. This would allow the removal of most of the modulo operations since the end of one page could be used to set up the next page.
 Have the threads write the results of each page as it is completed. If they each write to their own file we can significantly reduce the total time. A cat can merge the results into a single file if required.
 Writing the pages as we go means we no longer need the entire sieve in memory, so the vector<bitset> can be dropped. This could mean handling far greater limits  but I suspect the running time might get a bit too long to be practical.
__________________
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.

21st March 2017, 05:08 AM

Registered User


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


Re: Programming Challenge  list prime numbers
Here's an example in Ada for listing the first N >= 1 primes. You can get Ada from the F25 repos (dnf install gccgnat libgnatdevel).
Save this as getPrimes.adb:
Code:
with Ada.Text_IO, Ada.Command_Line; use Ada.Text_IO, Ada.Command_Line;
Procedure getPrimes is
Arg : String := Argument(1);
N : Integer := Integer'Value(Arg); P : Integer := 3; Counter : Integer := 1;
Function isPrime (Odd : Integer) Return Boolean is
Result : Boolean := True; I : Integer := 5;
Begin
If Odd > 3 Then
If Odd Mod 3 = 0 Then
Result := False;
Else
While I*I <= Odd Loop
If (Odd Mod I = 0 Or Odd Mod (I+2) = 0) Then
Result := False;
Exit;
End If;
I := I + 6;
End Loop;
End If;
End If;
Return Result;
End isPrime;
Begin
Put_Line (Integer'Image(2));
While Counter < N Loop
If isPrime(P) Then
Put_Line (Integer'Image(P));
Counter := Counter + 1;
End If;
P := P + 2;
End Loop;
End getPrimes;
Compile like this:
Code:
$ gnatmake gnatws getPrimes
Sample time for the first million primes:
Code:
$ time ./getPrimes 1000000 > primes.log
real 0m6.715s
user 0m5.855s
sys 0m0.794s
__________________
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

21st March 2017, 07:21 PM

Registered User


Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157


Re: Programming Challenge  list prime numbers
It would be nice to see how our results compare against each other in terms of time and space on one machine. I know Rupert has done time ranking in other threads, and I don't want to ask him to manually curate that as a computer should be able to do it. Maybe that should be a programming challenge; to setup something that can scrape the thread for our code and rank it.
__________________
OS: Arch Linux x86_64
Laptop: Lenovo ThinkPad L440, CPU: Intel Core i7 4702MQ Quad Core 2.20 GHz, Ram: 16GB DDR3, Hard Drive: 500GB, Graphics: Intel 4600 HD, Wireless: Intel 7260AC

26th March 2017, 07:59 PM

Registered User


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


Re: Programming Challenge  list prime numbers
Here's an example in Smalltalk for listing the first N >= 1 primes, using GNU Smalltalk (dnf install gnusmalltalk).
Save this as getPrimes.st:
Code:
isPrime := [ :m 
res i
res := true.
i := 5.
(m > 3) ifFalse:[res := true] ifTrue:[
(m\\3 == 0) ifTrue:[
res := false] ifFalse:[
[(i*i <= m) & res] whileTrue:[
((m\\i == 0)  (m\\(i+2) == 0)) ifTrue:[res := false].
i := i+6.]]].
res.
].
N := (Smalltalk arguments at:1) asInteger.
p := 3.
counter := 1.
'2' display.
[counter < N] whileTrue:[
(isPrime value:p) ifTrue:[
(', ', p asString) display.
counter := counter+1.
].
p := p+2.
].
'' displayNl.
Running the program to list the first 100 primes:
Code:
$ gst q getPrimes.st a 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
__________________
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

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: 18:44 (Friday, 21072017)







