Making a more efficient prime number program-'challenge'

[TeeK]

So i got the idea to make a prime number program that outputs the prime numbers from 0 to whatever limit the user inputs. I didn't manage to make the program calculate from 0 to the limit, so i made it go from 2 and up(i'm a noob coder).
So i bring a 'challenge' to the people on this forum, can you modify my code to make it do less calculations to find all the primes, or make your own with other rules for primes (i dont know any other at the top of my head other than throw all even numbers ,except 2, in the trash without 'testing' them)

who can make the most effective ? :)

with this program i managed to find all primes from 2 to
10 with 16 calculations
100 with 1134 calculations
1000 with 78023 calculations
10000 with 5775224 calculations
100000 with 455189151 calculations
1000000 with -1087379171 calculations (too many for int i guess)

  #include <iostream>
using namespace std;

int main()
{
	int limit;
	int i=2;
	int j;
	int k;
	int calculations=0;
	cout<<"Lets search for primes ! How far shall we go?"<< endl;
	cin>>limit;

	while(i<=limit)
	{
		if(i==2){ cout<<i<< endl; calculations ++; goto end;}
		else
		{
			j=2;
			k=0;
		}
		  while(j!=i && j!=1)
		  {
			  if (i%j==0)
			  {
				calculations ++;
				goto end;

			  }

			  calculations++;
			  j++;

		  	 }
		  	cout<<i<< endl;
		  	end:
			i++;
		  }
	cout<<"We found all the primes! It took "<<calculations<<" calculations to find all the primes from 2 to "<<limit<<"!"<< endl;

	return 0;
}

[fg109]

10: 11
100: 199
1000000: 3122043

#include <iostream>
#include <cmath>
#include <cstring>

//use the Sieve of Eratosthenes to find primes below limit

int main()
{
    unsigned long long limit, numCalcs = 0;
    bool *IsPrime;
    bool noMorePrimes = false;
    unsigned long long i = 2;

    std::cout << "Lets search for primes ! How far shall we go?\n";
    std::cin >> limit;

    IsPrime = new bool[limit];
    memset(IsPrime, true, sizeof(bool) * limit);
    IsPrime[0] = IsPrime[1] = false;

    while ((i < limit) && !noMorePrimes)
    {
        noMorePrimes = true;
        for (unsigned long long j = i; j * i < limit; ++j)
        {
            IsPrime[i*j] = false;
            ++numCalcs;
        }
        for (unsigned long long j = i + 1; j < limit; ++j)
        {
            ++numCalcs;
            if (IsPrime[j])
            {
                i = j;
                noMorePrimes = false;
                break;
            }
        }
    }

    std::cout << "We found all the primes! It took " << numCalcs
              <<" calculations to find all the primes from 2 to " << limit <<"!";
    delete[] isPrime;
    return 0;
}

EDIT: Forgot to delete the dynamic array.

Also, I guess numCalcs isn't really accurate, it's only counting how many times the program goes through each of the inner loops. Each time through a loop, it would increment the counter and do a comparison check for the condition, which is two calculations. And in my second inner loop, the code in the if statement would be another two calculations...

[Smac89]

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

using ull = unsigned long long;

int main() {
    vector<ull> factors = {3, 5, 7, 11, 13, 17, 19, 23};
    size_t len = factors.size();
    ull limit;
    cout << "Lets search for primes ! How far shall we go?" <<  endl;
    cin >> limit;

    int calcs = 0;
    for (ull p = 29; p <= limit ; p +=2) {
        bool isprime = true;
        ull sq = sqrt(p);
        for (size_t f = 0; f < len && factors[f] <= sq; f++) {
            calcs++;
            if (p % factors[f] == 0) {
                isprime = false;
                break;
            }
        }
        calcs++;
        if (isprime) {
            factors.push_back(p);
            len++;
        }
    }
    
    // for (ull& p : factors) {
    // 	cout << p << " ";
    // }
    

    cout << "We found all the primes! It took "
            << calcs << " calculations to find all the primes from 2 to "
            << limit << "!" <<  endl
            << "The number of primes from 2 to 1000000 is " << len << endl
            << "This means that it takes approximately " << (static_cast<double>(calcs) / len)
            << " calculations per prime to find all the primes\n";

    return 0;
}

----

Lets search for primes ! How far shall we go?
We found all the primes! It took 13427380 calculations to find all the primes from 2 to 1000000!
The number of primes from 2 to 1000000 is 78497
This means that it takes approximately 171.056 calculations per prime to find all the primes

EDIT:
Seems that prime factorization is not as effective as I thought it should be

[TeeK]

Great input ! I have a lot to learn :)