Elysian Shadows

Posted: **Thu Nov 13, 2008 11:09 am**

this challenge is basic and im sure everyone can part take.
challenge is to write a program that prints out consecutive primes up to prime closest to 100000.
winner is who ever program does it in the least time. any language is fair game. note however that you must use the program to tell you what your execution time was.

NB:: prime is a number that is only divisible by one and it self. (so that there is no remainder)
NOTE: 1 is not considered to be prime.
2,3,5,7,11,13....

here is one performance hint i can give you. you only have to test from 2 to floor(sqrt(X)) to see if X is prime. // that saves alot of time.
example: if we are testing if X = 53 is prime, sqrt(53) = 7.2801 floor(7.2801..) = 7.

so we only need to test 53%2 trough 53%7, if none of those are 0, then 53 is prime, which incidentally it is.

also if you really wanna go deep, look into sieve of aikin or somthing to that effect.

this is one of my favorite challenges because you can always make your program better. btw, if you can develope a really good prime algoritm you will never have to work in your like again.

Prime numbers are a big part of cryptography and thus people are willing to pay millions upon millions for prime number technology.

Posted: **Thu Nov 13, 2008 3:53 pm**

Hey everyone, long time viewer here... first time poster. Its extremely inspiring what you guys do. I'll give a more formal introduction in the future =P
anyways, here's a shot at the prime number question. Pretty sure it works although its slow ~O(n^2)

Code: Select all

#include <iostream>
#include <vector>
#include <math.h>

using std::cout;
using std::vector;


int main()
{
	vector<int> PrimeNumbers;

	PrimeNumbers.push_back( 2 );

	int nNum;

	for(int i = 3; i < 100000; i++)
	{

		nNum = static_cast<int>( floor( sqrt( static_cast<float>(i) ) ) );
		
		for( int j = 0; j < PrimeNumbers.size(); j++ )
		{
			if( i % PrimeNumbers.at(j) == 0 )
			{
				nNum = 0;
				break;
			}
			if( nNum < PrimeNumbers.at(j) )
				break;
		}

		if( nNum != 0 )
			PrimeNumbers.push_back( i );
	}

	for(int i = 0; i < PrimeNumbers.size(); i++ )
		cout << PrimeNumbers.at(i) << "\n";
	cout << PrimeNumbers.size() << "\n";

}

Posted: **Thu Nov 13, 2008 5:00 pm**

I didn't have enough time to write a timer, but the sieve of eratosthenes is probably on of the fastest ways to do it. I cooked this code up quickly, so if I have made any mistakes I apologize. Later.

Code: Select all

#define MAX 10000
int *ListA(NULL), *ListB(NULL);          
	ListA = new int [MAX];
	ListB = new int [MAX];                   // Could be set dynamically with a prompt 
		
for(int i = 0; i < MAX ; ++i){
	ListA[i] = i + 2; ListB[i] = EMPTY;  // Set inital values 
}
bool InitDone = false;                          
int  Test = MAX - 1;                            
for(int i = 0, j = 0; i < MAX ; ++i){           
	if(!(ListA[i]%ListB[j]) && !InitDone)       
		ListA[i] = EMPTY;                       
	if(i == Test && !InitDone){                 
		i = 0; InitDone = true;                 
		continue;                              
	}
	if(InitDone && ListA[i] == EMPTY) continue; 
	if(InitDone && ListA[i] != EMPTY){         
		j++; ListB[j] = ListA[i];              
		InitDone = false; i = 0;                
		continue;                             
	}
	if(j == Test) break;                        
}

Posted: **Fri Nov 14, 2008 10:03 am**

sparda wrote:I didn't have enough time to write a timer, but the sieve of eratosthenes is probably on of the fastest ways to do it. I cooked this code up quickly, so if I have made any mistakes I apologize. Later.

Code: Select all

#define MAX 10000
int *ListA(NULL), *ListB(NULL);          
	ListA = new int [MAX];
	ListB = new int [MAX];                   // Could be set dynamically with a prompt 
		
for(int i = 0; i < MAX ; ++i){
	ListA[i] = i + 2; ListB[i] = EMPTY;  // Set inital values 
}
bool InitDone = false;                          
int  Test = MAX - 1;                            
for(int i = 0, j = 0; i < MAX ; ++i){           
	if(!(ListA[i]%ListB[j]) && !InitDone)       
		ListA[i] = EMPTY;                       
	if(i == Test && !InitDone){                 
		i = 0; InitDone = true;                 
		continue;                              
	}
	if(InitDone && ListA[i] == EMPTY) continue; 
	if(InitDone && ListA[i] != EMPTY){         
		j++; ListB[j] = ListA[i];              
		InitDone = false; i = 0;                
		continue;                             
	}
	if(j == Test) break;                        
}

yes this is one of the fastest way to go... BUT, one of the most if not the most memory inefficient ways.
but i like your solutions.

edit. there were you said that it could be set dynamically, well that a misnomer. dynamically means it can change throughout runtime.
you can variable the input though.

Elysian Shadows

Prime challenge

Prime challenge

Re: Prime challenge

Re: Prime challenge

Re: Prime challenge