Click here to Skip to main content
15,357,967 members
Please Sign up or sign in to vote.
1.07/5 (9 votes)
See more:
Python
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


Python
a = asallar(1000000)
print a[9999]


Python
timeit asallar(1000000)


What I have tried:

Changed title in hopes trolls may avoid this post
Posted
Updated 2-Oct-21 5:44am
v3

C++
#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.
KarstenK 27-May-21 11:27am
   
Isnt the vector <bool> nov only needed to calculated ONCE?
Other point: nov[i] isnt needed this way, but a start value and recalculated when a "hit" was done?
For C, something like in the comments:

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900