Skip to main content
gamedev.net
🔒 Locked

C# question.

Started by Rick D 3 replies 550+ views
Original Post
Rick D
Rick D
I am a very early programmer, just working with basics programming right now. I have to make a program that takes the numbers 1 through 100 and finds all the prime numbers then prints out the average on screen. The following is what I had thought to try originally but though it prints to the screen all the primes from 11 through 97 correctly, it does not print 2,3,5,7. Reason for that is all those numbers mod themselves equal 0 thus they wont print. Also end result I will of course need to print the average rather than the actual primes but I am having it print the primes right now just so that I know they are all being processed correctly. Any hints on what else I should try? I am not looking for someone to do this for me, I won't learn by others doing the work. But if a hint could be dropped that would be helpful. Thanks :) { int primeNumber = 2; while (primeNumber <= 100) { if(primeNumber % 2 != 0 && primeNumber % 3 != 0 && primeNumber % 5 != 0 && primeNumber % 7 != 0) Console.WriteLine(primeNumber); primeNumber = primeNumber + 1; } }
squashed_bug
squashed_bug
What would happen if you needed to find primes between 1 and 121, then between 1 and 169 ... Maybe a second loop could help.
yaroslavd
yaroslavd
Yeah, you want to make programs that are easily scalable, modifiable, and extensible. So printing out the first 100 primes should be easy as print out the first 5. What you are doing right now, you might as well be saying Console.Writeline("2, 3, 5, 7, 11, 13..."). What you want is another loop. What it has to do is go from one to the square root of the number you are testing and check whether it's divisible. So let's say that you are trying to see if 101 is prime. You would basically loop through numbers 1 through 10 and see if (101 % i) == 0. You can't just assume that if a number isn't divisible by 2,3,5,7 that it's prime. How about 11*13 = 143? That's divisible by neither of the above, yet is obviously not prime.
Rick D
Rick D
Thanks for the pointers, I will go back in and look at it somemore. Thank you all for the insight.
Grain
Grain
Look up the “Sieve of Eratosthenes”
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Here is a S.O.E. implementation. It fills the vector with all the primes from 2 to n. Although and not exactly a true Sieve of Eratosthenes as it doesn’t fill the vector first. It checks if a number is prime first then adds it in. instead of going removing non primes from a full vector.
void Sieve(std::vector<unsigned int>& s ,unsigned int n) {    unsigned int m,i;    std::cout << "Calculating primes: " <<  std::endl <<  std::endl;    s.erase(s.begin(),s.end());    s.push_back(2); //Seed the vector with the first prime number: Two.    unsigned int root = 2;    for(m=3; m<=n; m+=2)     {        unsigned int count = s.size();        bool prime = true;	    while(root*root < m) root++;        for (unsigned int i = 0; i < count && s <= root; ++i)         {            if (!(m % s)) // current value is divisible by a former prime,discard it            {                 prime = false; break;            }        }        if (prime) s.push_back(m);    }    std::cout << s.size() << " primes calculated." << std::endl;}


Also here is a significantly faster implementation. I banged this out a while ago with the help of a few of the other members here.

Here the primes aren’t stored directly but rather are identified by their index in the “bit array”. If the bit is true than that index is prime.

void Sieve(bits& s ,unsigned int n){	unsigned int m,i,k;	    	std::cout << "Filling set: " << 1 << " to " << n << std::endl << std::endl;	s.resize(n);	s.set();	s.clear(0);	s.clear(1);		std::cout << "Set Filled, " /*<< s.size() << " Items."<< std::endl /**/;	std::cout << "Removing non-primes:" << std::endl << std::endl;		m = 0;	for(i=0; i < n; i++)        {		if(s)		{			m++;			for(k = (i+i); k < n; k+=i)				s.clear(k); 		}        }		std::cout << "Non-primes removed: " << m << " items remaining" << std::endl;}

The above requires the bits class.
#include <vector>class bits{	std::vector<unsigned char> B;public:	bits(unsigned int size)	{		B.resize(1 + size/8);	}	void resize(unsigned int size)	{		B.resize(1 + size/8);	}	unsigned int size()	{		return B.size()*8;	}	void set(unsigned int bit)	{		unsigned int p = bit/8;		unsigned int b = bit%8;		unsigned char m = 1 << b;		B = B | m;	}	void set()	{		for(unsigned int i = 0; i < this->size(); i++)			set(i);	}	void clear(unsigned int bit)	{		unsigned int p = bit/8;		unsigned int b = bit%8;		unsigned char m = 1 << b;		m = ~m;		B = B & m;	}	void clear()	{		for(unsigned int i = 0; i < this->size(); i++)			clear(i);	}		bool operator [](unsigned int bit)	{		unsigned int p = bit/8;		unsigned int b = bit%8;		unsigned char m = 1 << b;		m = m & B;		m = m >> b;		return m;	}};

Here is the discussion that lead to this:
http://www.gamedev.net/community/forums/topic.asp?topic_id=329905

[Edited by - Grain on August 1, 2006 2:21:28 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.