Fedora Linux Support Community & Resources Center
  #31  
Old 18th March 2017, 08:20 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,517
linuxfedorafirefox
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 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #32  
Old 18th March 2017, 08:50 PM
Flounder Offline
Registered User
 
Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157
linuxchrome
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
Reply With Quote
  #33  
Old 19th March 2017, 05:49 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,517
linuxfedorafirefox
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 Ctrl-c 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 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #34  
Old 19th March 2017, 07:47 AM
ocratato Online
Registered User
 
Join Date: Oct 2010
Location: Canberra
Posts: 2,499
linuxfirefox
Re: Programming Challenge - list prime numbers

Quote:
Originally Posted by RupertPupkin View Post
Flounder, I'm surprised you didn't do a Perl example. Here's one that lists all the primes (hit Ctrl-c 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.
Reply With Quote
  #35  
Old 19th March 2017, 02:47 PM
ocratato Online
Registered User
 
Join Date: Oct 2010
Location: Canberra
Posts: 2,499
linuxfirefox
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.
Reply With Quote
  #36  
Old 19th March 2017, 04:11 PM
bobx001 Offline
Registered User
 
Join Date: Dec 2012
Location: santa barbara, CA
Posts: 388
linuxfedorafirefox
Re: Programming Challenge - list prime numbers

Quote:
Originally Posted by ocratato View Post
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 ?
Reply With Quote
  #37  
Old 19th March 2017, 05:54 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,517
linuxfedorafirefox
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 (make-vector (+ n 1) #t)))
      (let loop ((p 2) (ps '()))
         (cond ((< n p) (reverse ps))
            ((vector-ref bits p)
               (do ((i (+ p p) (+ i p))) ((< n i))
                  (vector-set! 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 --no-auto-compile -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 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #38  
Old 20th March 2017, 05:38 AM
ocratato Online
Registered User
 
Join Date: Oct 2010
Location: Canberra
Posts: 2,499
linuxfirefox
Re: Programming Challenge - list prime numbers

Here is my multi-threaded 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<numPages-1; 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-1) * BITSETSZ;
		for( ul64 i=0; (x+i)<=limit; i++ )
		{
			if( primes[numPages-1][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.
Reply With Quote
  #39  
Old 20th March 2017, 09:27 AM
Flounder Offline
Registered User
 
Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157
linuxchrome
Re: Programming Challenge - list prime numbers

Quote:
Originally Posted by RupertPupkin View Post
Flounder, I'm surprised you didn't do a Perl example. Here's one that lists all the primes (hit Ctrl-c 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 non-prime 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
Reply With Quote
  #40  
Old 20th March 2017, 10:21 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,517
linuxfedorafirefox
Re: Programming Challenge - list prime numbers

Quote:
Originally Posted by Flounder View Post
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 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #41  
Old 21st March 2017, 12:15 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,517
linuxfedorafirefox
Re: Programming Challenge - list prime numbers

Quote:
Originally Posted by ocratato View Post
Here is my multi-threaded 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<numPages-1; 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[numPages-1][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 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #42  
Old 21st March 2017, 01:56 AM
ocratato Online
Registered User
 
Join Date: Oct 2010
Location: Canberra
Posts: 2,499
linuxfirefox
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 off-by-one error - now fixed in the original post.

I am using an Intel i5 processor: i5-2430M CPU @ 2.40GHz
This has two cores with "hyper-threading". 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 ./primes4-1 1000000000 > primes4.dat

real	0m12.807s
user	0m12.315s
sys	0m0.495s
[brenton@acer primes]$ time ./primes4-2 1000000000 > primes4.dat

real	0m8.871s
user	0m12.899s
sys	0m0.503s
[brenton@acer primes]$ time ./primes4-4 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 "hype-rthreading" 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.
Reply With Quote
  #43  
Old 21st March 2017, 05:08 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,517
linuxfedorafirefox
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 gcc-gnat libgnat-devel).

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 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
  #44  
Old 21st March 2017, 07:21 PM
Flounder Offline
Registered User
 
Join Date: Dec 2005
Location: Arkansas
Age: 28
Posts: 1,157
linuxchrome
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
Reply With Quote
  #45  
Old 26th March 2017, 07:59 PM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,517
linuxfedorafirefox
Re: Programming Challenge - list prime numbers

Here's an example in Smalltalk for listing the first N >= 1 primes, using GNU Smalltalk (dnf install gnu-smalltalk).

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 Dual-Core 5000+ 2.6GHz | RAM: 7GB PC5300 DDR2 | Disk: 400GB SATA | Video: ATI Radeon HD 4350 512MB | Sound: Realtek ALC888S | Ethernet: Realtek RTL8201N
Reply With Quote
Reply

Tags
challenge, list, numbers, prime, programming

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Programming Challenge: Create a list of X random numbers between Y and Z sea Programming & Packaging 6 14th December 2015 05:28 AM
A programming challenge. lsatenstein Programming & Packaging 3 4th January 2015 03:04 AM
Programming Challenge: Comparing Numbers in a String Flounder Programming & Packaging 23 10th January 2014 02:53 PM
[BASH]: Prime Numbers sea Guides & Solutions (Not For Questions) 14 21st November 2012 09:18 AM
Program to find prime numbers renkinjutsu Programming & Packaging 9 4th September 2011 07:40 AM


Current GMT-time: 01:43 (Friday, 26-05-2017)

TopSubscribe to XML RSS for all Threads in all ForumsFedoraForumDotOrg Archive
logo

All trademarks, and forum posts in this site are property of their respective owner(s).
FedoraForum.org is privately owned and is not directly sponsored by the Fedora Project or Red Hat, Inc.

Privacy Policy | Term of Use | Posting Guidelines | Archive | Contact Us | Founding Members

Powered by vBulletin® Copyright ©2000 - 2012, vBulletin Solutions, Inc.

FedoraForum is Powered by RedHat