That's Lot Of Primes!

Computer Science Level 2

Calculate the number of primes between $1$ to $10^6$ .

The answer is 78498.

6 solutions

Ankit Nigam
Mar 13, 2016

This is my solution. I am looking for more efficient way to solve this problem because my solution takes almost 1.95 sec.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

bool isprime(ll n){
  if(n == 2 || n == 3) return true;
  double y = sqrt(n);
  int x = floor(y);
  for(int i = 2; i <= x; i++){
    if(n % i == 0){
      return false;
      break;
    }
    if(n % i != 0 && i == x) return true;
  }
}

int main(){
  int d = 0;
  for(ll i = 2; i <= 1000000; i++){
    if(isprime(i)) d++;
  }
  cout << d;
  return 0;
}

Moderator note:

Good approach demonstrated. There are several optimizations that we could make, especially when we apply some number theoretic results.

There's the first minor improvement you can make in your checking for loop. Once you check n %2, if n %2==1 you no longer need to check n%k for any odd k. Likewise, you only need to check n%3 not n%6, or n%9 etc. This implies that you only need to check n%p for primes p.

This observation leads to two methods:

Iterate across all the numbers from 1 to 10^6 and maintain a vector of all the primes you encounter. When checking a new number X, you only need to check possible factors of p from your vector of primes, up to sqrt(X) still.
A Sieve of Eratosthenes which is similar to the first method. You can read the wikipedia article for the pseudocode and more details, but basically you store an array of the numbers from 1 to 1,000,000 and mark numbers as prime starting from the left. Once you mark a number as prime, mark all its multiples as composite. At the end, go through your array and count all those marked as prime.

//Method 1, 0.26s on cloud9.io with no optimization
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

int main(){
    vector<int> primes={2};
    for (int x=3;x<=1000000;x++){
        bool isPrime=true;
        for (int j=0;j<primes.size();j++){
            if (x%primes[j]==0){
                isPrime=false;
                break;
            }
            if (primes[j]>sqrt(x)) break;
        }
        if (isPrime) primes.push_back(x);
    }
    cout<<primes.size()<<endl;
    return 0;
}

//Method 2, 0.023s in cloud9.io with no optimization
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

bool isPrime[1000001];

int main(){
    memset(isPrime,true,sizeof isPrime);
    isPrime[0]=false;
    isPrime[1]=false;
    for (ll i=2;i<=1000000;i++){
        if (isPrime[i]){
            for (ll j=i;i*j<=1000000;j++) isPrime[i*j]=false;
        }
    }
    int count=0;
    for (int i=2;i<=1000000;i++) if (isPrime[i]) count++;
    cout<<count<<endl;
    return 0;
}

Andrew Lin - 5 years, 2 months ago

Another improvement because my Sieve wasn't ideal, you can stop checking primes once you past sqrt(1000000):

//Method 2, 0.017s in cloud9.io with no optimization
#include <iostream>
#include <cstring>
using namespace std;

bool isPrime[1000001];

int main(){
    memset(isPrime,true,sizeof isPrime);
    isPrime[0]=false;
    isPrime[1]=false;
    for (int i=2;i*i<=1000000;i++){
        if (isPrime[i]){
            for (int j=i;i*j<=1000000;j++) isPrime[i*j]=false;
        }
    }
    int count=0;
    for (int i=2;i<=1000000;i++) if (isPrime[i]) count++;
    cout<<count<<endl;
    return 0;
}

Andrew Lin - 5 years, 2 months ago

This is great idea!!

Ankit Nigam - 5 years, 2 months ago

This is my solution, and it's almost 2 times faster than yours.

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

typedef unsigned short usint;
typedef unsigned uint;

bool prime(uint* x) {
    float kk = sqrt(*x);
    usint t1;
    for (t1 = 2; t1 <= kk; ++t1) {
        if (*x % t1 == 0) return false;
    }
    return true;
}

uint ipb(uint* num) {
    uint t1 = 2, c = 0;

    while (t1 < *num) {
        if (prime(&t1)) ++c;
        if (t1 > 2) t1 += 2; else ++t1;
    }
    return c;
}

int main() { ios_base::sync_with_stdio(0);

    uint num = 1000000;
    cout << ipb(&num) << '\n';


    return 0;
}

Nikola Grujic - 5 years, 2 months ago

Nice. You should post this as a solution.

Ankit Nigam - 5 years, 2 months ago

Dude double x not int x ,else first thing your Programme do if pop a error

Sichen Wan - 5 years, 2 months ago

Actually we required to check upto floor of square root. That's why i didn't take double.I have edited my solution.

Ankit Nigam - 5 years, 2 months ago

Nikola Grujic
Mar 18, 2016

Sieve of Eratosthenes in C++. The running time is below 0.1 sec.

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

typedef unsigned short usint;
typedef unsigned uint;
typedef unsigned long ulint;


uint ipb() {
    bool niz[1000001];
    memset(niz, 1, sizeof(niz));
    uint c = 0, t1, t2;
    float kk = sqrt(1000000);

    for (t1 = 2; t1 <= kk; ++t1) {
        if (niz[t1]) {
            for (t2 = 2; t1*t2 <= 1000000; ++t2) {
                niz[t1*t2] = 0;
            }
        }
    }

    c = count(niz+2, niz + 1000001, 1);
    return c;
}

int main() { ios_base::sync_with_stdio(0);

    cout << ipb() << '\n';


    return 0;
}

You can speed this up dramatically by starting t2 at t1+1

Edit: start t2 at t1, not t1+1

Andrew Lin - 5 years, 2 months ago

No.... When using Sieve of Eratosthenes, we make a bool array (or a bitset..) and make all numbers primes. Then, t1 starts from 2, so it's prime and every 2*t2 number is not a prime.. And t1 goes to sqrt(1000000).

Nikola Grujic - 5 years, 2 months ago

Yes I know, you can see my solution above where I start t2 at t1. When t1 is prime, you only need to check multiples of t1 larger than or equal to t1^2, since any composite number smaller than that will have a prime factor smaller than t1 as well, so you already marked it as false. e.g. once you remove all multiples of 2, and you mark 3 as prime, you no longer need to do 2 * 3, you can go straight to 3 * 3.

Andrew Lin - 5 years, 2 months ago

Sébastien Laberge
Mar 18, 2016

Certainly not the most efficient way to do this, but this Python solution works, slowly but surely. I got the value 78,498.

# Maximum value to check for primeness
maxValue = 10**6

# Python list to contain every prime integer below maxValue
# We initialize it with 2, which we know to be the first prime number
primeList = [2]

# Current value to check for primeness
# We initialize it to 3, the first value to check after 2
currentValue = 3

# Main loop
while currentValue <= maxValue:
  # Print progress every 10%
  if ((currentValue+1) % (maxValue//10)) == 0:
    print("%i%%" % (1+currentValue/maxValue*100))

  # To be set later to False if currentValue is not prime
  isPrime = True

  # Loop over every prime number found so far
  for i in range(len(primeList)):
    # Check if primeList[i] is a divisor of currentValue 
    # If so, we know right away that currentValue isn't prime.
    if currentValue % primeList[i] == 0:
      isPrime = False
      break

  # If we went through the loop without finding a single divisor of
  # currentValue among the previously found prime numbers, then isPrime
  # is still set to True and we know currentValue is itself prime.
  if isPrime:
    primeList.append(currentValue)

  # Increment currentValue for next iteration
  # We increment by 2 to skip even numbers, which we know not to be prime
  currentValue += 2

# Print how many primes there are between 1 and maxValue
print("Solution: %i" % len(primeList))

Hasmik Garyaka
Sep 8, 2017

static bool checkPrime(long n) { if (n == 1) return false; if (n == 2 || n == 3) return true; if ((n + 1) % 6 != 0 && ((n - 1) % 6 != 0)) return false;

        long i = Convert.ToInt64(Math.Sqrt(n));
        for (; i >= 5; i--)
        {
            if ((i + 1) % 6 != 0 && ((i - 1) % 6 != 0)) continue;
            if (n % i == 0)
                return false;
        }
        return true;
    }
    static void Main(string[] args)
    {
        int i = 1;
        int x=0;
        for (i = 1; i <= 1000000; i++)
        {
            if(checkPrime(i))
           {
               x++;
           }

}

Rushikesh Jogdand
May 10, 2016

def isprime(n):
    if n<=1:
        return False
    elif n<4:
        return True
    elif n%2==0 or n%3==0:
        return False
    elif n<9:
        return True
    elif n%5==0:
        return False
    else:
        k=5
        while k<(n**0.5+1):
            if n%k==0 or n%(k+2)==0:
                return False
            k=k+6
        return True

Yehuda Davis
Apr 28, 2016

This is my solution in visual studio but it takes a few minutes when I just want the amount of prime numbers when I want to also know all the prime numbers it takes at least a hour

Public Class Form1 Dim ln As Integer Dim wtd As Integer Private Sub Button2_Click(sender As Object, e As EventArgs) Handles Button2.Click For ln = TextBox1.Text To TextBox2.Text If Not ln Mod 2 = 0 Then For wtd = 2 To ln / 2 + 0.5 If ln Mod wtd = 0 Then Exit For ElseIf wtd = ln / 2 + 0.5 Then If CheckBox1.Checked = True Then TextBox1.Text = TextBox1.Text + 1 End If If CheckBox2.Checked = True Then TextBox2.Text = TextBox2.Text & ln & " " End If End If Next End If Next End Sub End Class

That's Lot Of Primes!

The answer is 78498.

6 solutions

Moderator note:

0 pending reports