14,667,169 members
Rate this:
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 12-Oct-20 1:17am
v2

Page 1 of 2

Rate this:

## 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.
Afzaal Ahmad Zeeshan 15-Mar-19 9:18am

5ed.
CPallini 18-Mar-19 3:47am

Thanks.
Rate this:

## 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

Page 1 of 2
1 2

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

Top Experts
Last 24hrsThis month
 OriginalGriff 165 Sandeep Mewara 70 KarstenK 65 PIEBALDconsult 55 Patrice T 52
 OriginalGriff 4,951 Richard MacCutchan 3,425 CPallini 2,082 Sandeep Mewara 1,525 Patrice T 1,256

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