473,320 Members | 2,097 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes and contribute your articles to a community of 473,320 developers and data experts.

Fast Prime Number List Generator

bartonc
6,596 Expert 4TB
Description:

This is a fast prime number list generator using sieve algorithm. This function return a list of prime numbers which <= argument.

Expand|Select|Wrap|Line Numbers
  1. def primes(n): 
  2.     if n==2: return [2]
  3.     elif n<2: return []
  4.     s=range(3,n+1,2)
  5.     mroot = n ** 0.5
  6.     half=(n+1)/2-1
  7.     i=0
  8.     m=3
  9.     while m <= mroot:
  10.         if s[i]:
  11.             j=(m*m-3)/2
  12.             s[j]=0
  13.             while j<half:
  14.                 s[j]=0
  15.                 j+=m
  16.         i=i+1
  17.         m=2*i+3
  18.     return [2]+[x for x in s if x]
  19.  
  20. print primes(13)
  21. print primes(3000)
  22.  
From ActiveState's Python Cookbook area (here).
------------- we get ------------
[2, 3, 5, 7, 11, 13]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163
, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251
, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349
, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443
, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557
, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647
, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757
, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863
, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983
, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 10
69, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171
, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 13
73, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471
, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 16
57, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753
, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 19
87, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081
, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 22
87, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381
, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 26
17, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699
, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 29
03, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999]
Jan 30 '07 #1
4 13230
kudos
127 Expert 100+
cool! but why do you do this?
Expand|Select|Wrap|Line Numbers
  1. half=(n+1)/2-1
since it equal to
Expand|Select|Wrap|Line Numbers
  1. half=n+1
ahhh..it really doesn't matter, I just felt like posting something :)
-kudos
Jan 30 '07 #2
horace1
1,510 Expert 1GB
cool! but why do you do this?
Expand|Select|Wrap|Line Numbers
  1. half=(n+1)/2-1
since it equal to
Expand|Select|Wrap|Line Numbers
  1. half=n+1
ahhh..it really doesn't matter, I just felt like posting something :)
-kudos
I would have thought that
Expand|Select|Wrap|Line Numbers
  1. half=(n+1)/2-1
would evaluate to
Expand|Select|Wrap|Line Numbers
  1. half=((n+1)/2)-1
according to the operator precedence rules
http://www.ibiblio.org/g2swap/byteof...recedence.html
Jan 30 '07 #3
bartonc
6,596 Expert 4TB
cool! but why do you do this?
Expand|Select|Wrap|Line Numbers
  1. half=(n+1)/2-1
since it equal to
Expand|Select|Wrap|Line Numbers
  1. half=n+1
ahhh..it really doesn't matter, I just felt like posting something :)
-kudos
That's the spirit! I miss seeing you avatar on posts these days.
Jan 31 '07 #4
kudos
127 Expert 100+
ahhhh....i completely forgot that...I should test code myself before I post...:-)

-kudos

I would have thought that
Expand|Select|Wrap|Line Numbers
  1. half=(n+1)/2-1
would evaluate to
Expand|Select|Wrap|Line Numbers
  1. half=((n+1)/2)-1
according to the operator precedence rules
http://www.ibiblio.org/g2swap/byteof...recedence.html
Feb 1 '07 #5

Sign in to post your reply or Sign up for a free account.

Similar topics

36
by: Dag | last post by:
Is there a python module that includes functions for working with prime numbers? I mainly need A function that returns the Nth prime number and that returns how many prime numbers are less than N,...
9
by: Greg Brunet | last post by:
In doing some testing of different but simple algorithms for getting a list of prime numbers, I ended up getting some results that seem a bit contradictory. Given the following test program...
11
by: lostinpython | last post by:
I'm having trouble writing a program that figures out a prime number. Does anyone have an idea on how to write it? All I know is that n > 2 is prim if no number between 2 and sqrt of n...
20
by: Tuvas | last post by:
I have made and recently posted a libary I made to do Modular Arithmetic and Prime numbers on my website at http://www.geocities.com/brp13/Python/index.html . I am currently in a crypotology...
10
by: Joel Mayes | last post by:
Hi All; I'm teaching myself C, and have written a prime number generator. It is a pretty inefficient implementation of the Sieve of Eratosthenes to calculate primes up to 1,000,000. If anyone...
5
by: maks | last post by:
Hi! I need some help in modifying this prime number generator code. How do I modify this code so that it assigns prime numbers to an array and returns it? I have tried to get it work but it...
7
by: Caffiend | last post by:
Well, I've been picking at learning python, got tired of reading, and figured I'd try to replicate my prime number generator I wrote (with much TSDN forum help) in C++. I've hit a stumbling block......
2
by: QHorizon | last post by:
Hello, I'm new to Python (I've learned everything up to iterators so far) and fairly new to Programming. This would be my first real program: #Coordinate Geometry (The whole program is not...
12
by: electric916 | last post by:
I have a homework assignment i Am totally confused on. I started with a basic code to determine if a number is prime or not, but need guidance from here. I will post assignment details then what I...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.