leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

count-primes.cpp (1186B)

      1 #include <iostream>
      2 #include <vector>
      3 #include <cmath>
      4 using namespace std;
      5 
      6 //This is the most optimized version I could get where it only checks values up to the square
      7 //root -1 of the original value, and it only checks odd numbers.
      8 //TLE FROM LEETCODE
      9 
     10 int countPrimes(int n) {
     11    vector <int> previous_primes;
     12    previous_primes.push_back(2);
     13     bool prime = true;
     14     if(n <= 2){
     15         return 0;
     16     }
     17     int cut_off = sqrt(n-1);
     18     for(int i = 3 ; i < n; ++++i){
     19         for(int x = 0 ; x < previous_primes.size(); ++x){
     20             if(i % previous_primes[x] == 0){
     21                 prime = false;
     22                 break;
     23             }
     24             if(previous_primes[x] > cut_off ){
     25                 break;
     26             }
     27 
     28         }
     29         if(prime){
     30             previous_primes.push_back(i);
     31             cout << i << " ";
     32 
     33         }
     34         else{
     35             prime = true;
     36         }
     37     }
     38     return previous_primes.size();
     39 }
     40 
     41 
     42 int main(){
     43   cout << "Enter number to find primes before: ";
     44   int prime_val;
     45   cin >> prime_val;  
     46   int vals = countPrimes(prime_val);
     47 
     48   cout << endl << endl << "The total number of primes before " << prime_val << " is " << vals << endl;
     49   
     50 
     51 }