Click here to Skip to main content
15,434,147 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.
 
Share this answer
 
Comments
Afzaal Ahmad Zeeshan 15-Mar-19 9:18am    
5ed.
CPallini 18-Mar-19 3:47am    
Thanks.
KarstenK 27-May-21 11:27am     CRLF
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
 
Share this answer
 

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