Why is my program so slow?

[Canucklehead]

#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.

[Canucklehead]

The other, faster program (which i changed a little to add a timer):

#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;
	}

[Salem]

> 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)