Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Poltifar]

Ok, so I've known a bit of many programming, scripting, and database query languages for some time, ranging from basic to php to mysql to javascript, but I've never really tried doing much with any of them short of learn the fundamental basics. This time, I've decided to delve deeper and actually try making something slightly noteworthy, and I decided to do so in C++ (since I figured that learning this one is better than learning a hundred less used programming languages (I'm not saying that other languages are not worth knowing though)).

I skimmed through the hello world tutorial quickly, but making something big (a Roguelike maybe?) is still a bit far off, so instead I made a prime number finder that uses the Sieve of Eratosthenes method to pick primes out of the other, less interesting numbers.

I'm gona give the source code, which I compile in Dev-C++ 4.9.9.2. Its inefficient, the code messy, its a HUGE memory hog if you try to search to big numbers, but hey, it works. And damn well for my first slighlty useful C++ program I'd say.

Code: [Select]


#include <iostream>
#include <string>
#include <sstream>
#include <math.h>

using namespace std;

main()
{
      string inputstr;
      long n=0;
      short tf=0;
      long maxnum;
      //int sieve[100]; //not used now, was for non-dynamic-array
      short * sieve;
      long currentfactor=2;
     
      newsearch:
      n=0; tf=0; currentfactor=2;
           
      cout << "Input the max number in our search (from 2 to 10000), or nothing to exit: ";
      getline (cin,inputstr) ;
      if (inputstr == "") return 0;
      stringstream(inputstr) >> maxnum;
     
      if (maxnum > 10000) maxnum = 10000;
      if (maxnum <= 1) maxnum = 2;
     
      cout << "The search will be up to " << maxnum << ", press enter to start.";
      getline (cin,inputstr) ;
     
      sieve = new short [maxnum];
     
      //maxnum=100; //for debugging only
     
      for (int i=0; i<maxnum; i++)
      {
          sieve[i]=1;
      }
      sieve[0]=0;
     
      sievethething:
                   
      n=0;
      tf=0;
     
      do {
          tf = sieve[n];
          n++;
      } while (tf != 1);
      currentfactor=n;
      n--;
      sieve[n]=2;
     
      while (n<maxnum) {
          if (sieve[n]==1) sieve[n]=0;
          n=n+currentfactor;
      }
     
      if ((currentfactor*currentfactor) < maxnum) goto sievethething;
      n=0;
      for (int i=0;i<maxnum; i++) {
          if (sieve[i]==1 || sieve[i]==2) { cout << (i+1) << " "; n++; }
      }
     
      cout << "\nNumber of primes found: " << n;
     
      delete [] sieve;
      getline (cin,inputstr) ; 
      goto newsearch;
}


Yeah, messymessymessy. I also forget to use comments most of the time, so its probably very hard to figure out.

I just felt like sharing this with the DF community that has many great programmers in it. I dont think I'll work on it much more, since i want to move on to something else, but I'm curious if there is another more efficient way to find primes. I thought about dividing each and every number by all numbers inferior to it, but I think that that way would be far slower, although less of a memory hog.

PS: I put a limit of 10000 to the max number in a search, but that can be tweaked in the code fairly easily if you want to murder your computer. I tried up to 500000 before I started getting bored of the slightly long wait.

EDIT: Fixed stuff up and added a 'number of primes found' line at the end of searches.

[Derakon]

There are faster approaches than the Sieve of Eratosthenes, but they tend to be much more complicated to implement. Eratosthenes is good enough for the first hundred or so Project Euler problems, which are very fond of primes.

For what it's worth, here's my own sieve implementation, in Python:

Code: [Select]

primeCache = [2]
maxN = 3
def primes(n):
    result = []
    for prime in primeCache:
        result.append(prime)
        if prime > n:
            return result

    if n <= maxN:
        return result

    nums = range(maxN, n+2, 2) # maxN is guaranteed odd when we set it
    newNums = []
    for num in nums:
        shouldAdd = 1
        for prime in primeCache:
            if num % prime == 0:
                shouldAdd = 0
                break
        if shouldAdd:
            newNums.append(num)
    nums = newNums

    while nums:
        prime = nums[0]
        result.append(prime)
        newNums = []
        for num in nums:
            if num % prime != 0:
                newNums.append(num)
        nums = newNums
    primeCache = result
    if n % 2 == 0:
        n -= 1
    util.maxN = n
    return result