Why is my program so slow?

This is a discussion on Why is my program so slow? within the C++ Programming forums, part of the General Programming Boards category; Code: #include <vector> #include <iostream> #include <cmath> using namespace std; int main(int argc, char *argv[]) { time_t start,end; time (&start); ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    10

    Why is my program so slow?

    Code:
    #include <vector>
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    int main(int argc, char *argv[]) {
        time_t start,end;
        time (&start);
    	int lastTry = atoi(argv[1]);
    	vector<int> PrimeList(1,2);
    	vector<int>::iterator a;
    	for (int numerator = 2; numerator <= lastTry; numerator++) {
            for (a = PrimeList.begin(); (a != PrimeList.end()) && (*a * *a <= numerator); a++) {
                if (numerator % *a) {} else {break;}
            }
            if (*a * *a > numerator) {
               PrimeList.push_back(numerator);
               cout << numerator << endl;
            }
        }
        PrimeList.clear();
        time (&end);
        double dif = difftime (end,start);
        cout << dif << endl;
    	return 0;
    }
    This program finds prime numbers.
    Why is it so slow compared to a similar program that I found on the internet that did this twice as fast?
    Are vectors really slow? The other program used a linked list.

  2. #2
    Registered User
    Join Date
    Sep 2005
    Posts
    10
    The other, faster program (which i changed a little to add a timer):

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <time.h>
    #include <iostream>
    using namespace std;
    typedef  unsigned long long bignum;
    
    struct primerec
    	{
    	bignum bn;
    	struct primerec * next;
    	};
    
    void printPrime(bignum bn)
    	{
    	static char buf[1000];
    
    	sprintf(buf, "%ull", bn);
    	buf[strlen(buf) - 2] = '\0';
    	printf("%s\n", buf);
    	}
    
    void freeList(struct primerec *head)
    	{
    	struct primerec *thisPrime = head;
    	while(1)
    		{
    		struct primerec *nextPrime = thisPrime->next;
    		free(thisPrime);
    		if(nextPrime == NULL)
    			break;
    		else
    			thisPrime = nextPrime;
    		}
    	}
    
    void findPrimes(bignum topCandidate)
    	{
    	struct primerec *firstPrime = (primerec*) malloc(sizeof(struct primerec));
    	assert(firstPrime != NULL);
    	struct primerec *latestPrime = firstPrime;
    	firstPrime->bn = 2;
    	firstPrime->next=NULL;
    	bignum candidate = 2;
    	while(candidate <= topCandidate)
    		{
    		struct primerec *thisPrime = firstPrime;
    		int prime = 1;
    		while(thisPrime->bn * thisPrime->bn <= candidate)
    			{
    			if(candidate % thisPrime->bn == 0)
    				{
    				prime = 0;
    				break;
    				}
    			thisPrime = thisPrime->next;
    			}
    		if(prime)
    			{
    			printPrime(candidate);
    			latestPrime->next = (primerec*) malloc(sizeof(struct primerec));
    			assert(latestPrime->next != NULL);
    			latestPrime = latestPrime->next;
    			latestPrime->bn = candidate;
    			latestPrime->next = NULL;
    			}
    		candidate++;
    		}
    	freeList(firstPrime);
    	}
    
    int main(int argc, char *argv[])
    	{
        time_t start,end;
        time (&start);
    	bignum topCandidate = 1000;
    	if(argc > 1)
    		topCandidate = atoll(argv[1]);
    	findPrimes(topCandidate);
    	time (&end);
    	double dif = difftime (end,start);
        cout << dif << endl;
    	return 0;
    	}

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    > for (int numerator = 2; numerator <= lastTry; numerator++)
    Well you can make it twice as fast by NOT checking all the even numbers.
    Say
    for (int numerator = 3; numerator <= lastTry; numerator += 2)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with a program, theres something in it for you
    By engstudent363 in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 12:41 PM
  2. Replies: 4
    Last Post: 02-21-2008, 09:39 AM
  3. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  4. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21