Click here to Skip to main content
14,209,666 members
Rate this:
Please Sign up or sign in to vote.
See more:
def asallar(limit):
   limitn = limit+1
   asal_degil = [False] * limitn
   asal_listesi = []
 
   for i in range(2, limitn):
       if asal_degil[i]:
           continue
       for f in xrange(i*2, limitn, i):
           asal_degil[f] = True
       asal_listesi.append(i)
 
   return asal_listesi


a = asallar(1000000)
print a[9999]


timeit asallar(1000000)
Posted
Updated 20-Apr-19 23:58pm
v2
Rate this:
Please Sign up or sign in to vote.

Solution 11

#include <iostream>
using namespace std;

vector <int>  asallar(size_t limit)
{
  vector <bool> nov(limit+1, false);
  vector <int> result;
  for (size_t i=2; i<=limit; ++i)
  {
    if ( nov[i] ) continue;
    for (size_t f = i*2; f<=limit; f+=i)
    {
      nov[f] = true;
    }
    result.push_back(i);
  }
  return result;
}

int main()
{
  auto v = asallar(1000000);
}


Timing:
Python program: about 300 ms
C++ program:    about 100 ms

Please note: if a vector<int> (instead of a vector<bool>) is used in the C++ program, then the execution speed is doubled.
   
Comments
Afzaal Ahmad Zeeshan 15-Mar-19 9:18am
   
5ed.
CPallini 18-Mar-19 3:47am
   
Thanks.
Rate this:
Please Sign up or sign in to vote.

Solution 1

For C, something like in the comments:

def asallar(limit): \\ void asallar(int limit, int* asal_listesi){
   limitn = limit+1 \\ int limitn =limit+1;
   asal_degil = [False] * limitn \\ int *asal_degil = malloc(...)
   asal_listesi = [] \\ vector asal_listesi; 
 
   for i in range(2, limitn): \\ for(int i=2; i<limitn;>       if asal_degil[i]: \\ if(asal_degil[i])
           continue       \\ continue;
       for f in xrange(i*2, limitn, i): \\ etc
           asal_degil[f] = True
       asal_listesi.append(i)
 
   return asal_listesi
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Advertise | Privacy | Cookies | Terms of Service
Web03 | 2.8.190617.3 | Last Updated 21 Apr 2019
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100