hello, i have another problem i feel that i have to be missing
something.. Basically, i've written a recursive function to find all
the prime up to a number (lim).. here is the function:
The function basically takes in a list of all the prime number found,
it takes the next number to be tested for (next) and the limit it will
go up to. It divide next by the list of previous prime numbers if next
is not bigger than lim, count up all the times where it's not evenly
divdided, if the result is equal the length of prime number, then we
have another prime number, lather rinse and repeat :)
def findPrime(seed, next, lim):
print("seed: " + str(seed) + " next: " + str(next) + " lim: " +
str(lim))
print(seed)
if(next >= lim):
print(seed)
return seed
else:
count = 0;
for num in seed:
modu = math.modf(float (next)/float(num));
if(modu[0] > 0):
count += 1
if(count == len(seed)):
seed.append(nex t)
findPrime(seed, next+2, lim)
else:
findPrime(seed, next+2, lim)
As you can probably see, i've printed the value of seed up until the
point where i'm returning the seed, however, the function still returns
None..
10  2433 
On 1/05/2006 2:52 PM, ra********@gmai l.com wrote: hello, i have another problem i feel that i have to be missing
something.. Basically, i've written a recursive function to find all
the prime up to a number (lim).. here is the function:
The function basically takes in a list of all the prime number found,
it takes the next number to be tested for (next) and the limit it will
go up to. It divide next by the list of previous prime numbers if next
is not bigger than lim, count up all the times where it's not evenly
divdided, if the result is equal the length of prime number, then we
have another prime number, lather rinse and repeat :)
def findPrime(seed, next, lim):
print("seed: " + str(seed) + " next: " + str(next) + " lim: " +
str(lim))
print(seed)
if(next >= lim):
print(seed)
return seed
else:
count = 0;
for num in seed:
modu = math.modf(float (next)/float(num));
if(modu[0] > 0):
count += 1
if(count == len(seed)):
seed.append(nex t)
findPrime(seed, next+2, lim)
else:
findPrime(seed, next+2, lim)
As you can probably see, i've printed the value of seed up until the
point where i'm returning the seed, however, the function still returns
None..
That's because it "falls off the end" of the function, which causes it
to return None. However that's not your only problem. Major other
problem is updating "seed" in situ.
Consider the following:
=== file: pseed.py ===
def findPrime(seed, next, lim):
print "seed: %r, next: %d, lim: %d" % (seed, next, lim)
if next >= lim:
return seed
for num in seed:
# modu = math.modf(float (next)/float(num));
# Try integer arithmetic:
if num > 2 and not (next % num):
# "next" is not a prime number
return findPrime(seed, next+2, lim)
return findPrime(seed + [next], next+2, lim)
# results:
""" pseed.findPrime ([1, 2], 3, 30)
seed: [1, 2], next: 3, lim: 30
seed: [1, 2, 3], next: 5, lim: 30
seed: [1, 2, 3, 5], next: 7, lim: 30
seed: [1, 2, 3, 5, 7], next: 9, lim: 30
seed: [1, 2, 3, 5, 7], next: 11, lim: 30
seed: [1, 2, 3, 5, 7, 11], next: 13, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13], next: 15, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13], next: 17, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17], next: 19, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19], next: 21, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19], next: 23, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 25, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 27, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 29, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29], next: 31, lim: 30
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
"""
# Doh! Looks like recursion not necessary. Google 'eliminate tail
recursion' :-)
def findPrime2(lim) :
seed = [1, 2]
for next in xrange(3, lim, 2):
prime = True
for num in seed:
if num > 2 and not (next % num):
prime = False
break
if prime:
seed.append(nex t)
return seed
# results:
""" pseed.findPrime 2(30)
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
""" ra********@gmai l.com wrote: The function basically takes in a list of all the prime number found,
it takes the next number to be tested for (next) and the limit it will
go up to. It divide next by the list of previous prime numbers if next
is not bigger than lim, count up all the times where it's not evenly
divdided, if the result is equal the length of prime number, then we
have another prime number, lather rinse and repeat :)
Your basic algorithm as described above sounds workable, but can be made
more efficient (I didn't look closely at your code for bugs). I won't even
go near the complicated number theory algorithms.
1. integer mod will be faster than floating point mod (unless you're getting
into numbers too large to store efficiently as ints, but you'll probably
run into other limitations before you get near that point in this code).
2. you can stop as soon as you find a zero remainder, no need to keep
testing the rest of the primes in the list.
3. you can stop testing numbers at the halfway point. there are no primes
smaller than 2, so no number x can have a factor larger than x/2.
4. in fact you can do even better. a simple proof by contradiction shows
that if primes 1..y don't divide x and y^2 > x then x must be prime. put
another way, once you test up to the square root of x, there's no point
continuing. if one factor were bigger than sqrt(x), the other would have
to be smaller than sqrt(x). but you've already tested the factors smaller
than sqrt(x), so there can't be any factors.
5. you can do better than checking every odd number (next+2) to find the
next prime, but I'm too tired to look into it right now. it may require
more complex machinery.
Locating primes is an interesting challenge because of the seemingly endless
grades of refinements over simple brute-force search. Like I said though,
if speed and size aren't concerns, your algorithm is fine.
Edward Elliott wrote:
[in reponse to some prime-number code] 5. you can do better than checking every odd number (next+2) to find the
next prime, but I'm too tired to look into it right now. it may require
more complex machinery.
You only need to check the prime numbers up to sqrt(n). If you're
calculating primes in sequential order, this is easy. Otherwise, you
can remove a third of the odd divisors by considering only odd numbers
of the form 6k±1 (because 6k±3 is divisible by 3).
def potential_prime s():
yield 2
yield 3
i = 6
while True:
yield i - 1
yield i + 1
i += 6 ra********@gmai l.com wrote:
Several people have already given you good answers as to why you're getting
None, and how to improve the algorithm you're using. I want to address
some stylistic questions.
First, is the if(next >= lim):
print(seed)
return seed
else:
count = 0;
[...]
construct. You don't need the else part, since the if clause ends with a
return. You can just un-indent one stop and put everything that is now
inside the "else" at the same level as the "if". This makes your program
easier to read and understand. Your program isn't too bad because it's
only got about a dozen lines of code in the "else", and you only end up
about 4 indents deep. In larger programs, you can end up with 100's of
lines of code and 5, 6, or more indents. Then it's a nightmare to
understand.
The other sylistic issue is this:
if(count == len(seed)):
seed.append(nex t)
findPrime(seed, next+2, lim)
else:
findPrime(seed, next+2, lim)
You've repeated the call to findPrime(). You refactor that out like:
if(count == len(seed)):
seed.append(nex t)
findPrime(seed, next+2, lim)
Three lines of code instead of five, and no repeated code. Easier to
understand.
John Machin wrote:
That's because it "falls off the end" of the function, which causes it
to return None. However that's not your only problem. Major other
problem is updating "seed" in situ.
I'm not sure what "falls off the end" of the function means, i searched
online, it seems to mean that the function has reached the end
prematurely and returned a default identifier to signal success or
not.. Can you please explain what that means?
Other than that, thanks alot for all those who posted! It's been very
educational! ra********@gmai l.com wrote: John Machin wrote:
That's because it "falls off the end" of the function, which causes it
to return None. However that's not your only problem. Major other
problem is updating "seed" in situ.
I'm not sure what "falls off the end" of the function means, i searched
online, it seems to mean that the function has reached the end
prematurely and returned a default identifier to signal success or
not.. Can you please explain what that means?
it means exactly what it says: that execution of the function body reaches
the end of the function without seeing an explicit "return" statement.
Python handles this by inserting an extra "return" statement at the end, to
make sure there's always something to return (a plain "return" returns None
to the caller).
</F>
Edward Elliott wrote: ra********@gmai l.com wrote: The function basically takes in a list of all the prime number
found, it takes the next number to be tested for (next) and the
limit it will go up to. It divide next by the list of previous
prime numbers if next is not bigger than lim, count up all the
times where it's not evenly divdided, if the result is equal the
length of prime number, then we have another prime number, lather
rinse and repeat :)
Your basic algorithm as described above sounds workable, but can be
made more efficient (I didn't look closely at your code for bugs). I
won't even go near the complicated number theory algorithms.
1. integer mod will be faster than floating point mod (unless you're
getting into numbers too large to store efficiently as ints, but
you'll probably run into other limitations before you get near that
point in this code).
2. you can stop as soon as you find a zero remainder, no need to keep
testing the rest of the primes in the list.
3. you can stop testing numbers at the halfway point. there are no
primes smaller than 2, so no number x can have a factor larger than
x/2.
4. in fact you can do even better. a simple proof by contradiction
shows that if primes 1..y don't divide x and y^2 > x then x must be
prime. put another way, once you test up to the square root of x,
there's no point continuing. if one factor were bigger than sqrt(x),
the other would have to be smaller than sqrt(x). but you've already
tested the factors smaller than sqrt(x), so there can't be any
factors.
The Prime Number article[1] on Wikipedia has a nice little Python
snippet implementing this algorithm (more or less). See the Finding
Prime Numbers section.
5. you can do better than checking every odd number (next+2) to find
the next prime, but I'm too tired to look into it right now. it may
require more complex machinery.
Locating primes is an interesting challenge because of the seemingly
endless grades of refinements over simple brute-force search. Like I
said though, if speed and size aren't concerns, your algorithm is
fine.
Further reading: the Sieve of Eratosthenes[2] is a relatively simple
and fun little algorithm to implement (also has a size issue in that it
requires a list of numbers from 2 up to the largest number you wish to
test for primality, and I don't think it's any faster than the
algorithm above). A modern refinement called the Sieve of Atkin[3] is
also interesting, a bit faster, although rather more complicated.
If you want to look further into the subject, see the Primality Test
article[4] on Wikipedia (mentions things like probabilistic testing,
the Miller-Rabin primality test, and such like).
[1] http://en.wikipedia.org/wiki/Prime_number
[2] http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
[3] http://en.wikipedia.org/wiki/Sieve_of_Atkin
[4] http://en.wikipedia.org/wiki/Primality_test
Dave.
--
On 1 May 2006 07:19:48 -0700, rumours say that ra********@gmai l.com might
have written: I'm not sure what "falls off the end" of the function means, i searched
online, it seems to mean that the function has reached the end
prematurely and returned a default identifier to signal success or
not.. Can you please explain what that means?
I think that you haven't grasped the fact that a chain of calls of a
recursive function needs a return for *every* invocation of the function
(but I could be wrong :)
Check the following function, analogous to your own: def f(x):
if x > 4:
print " returning", x
return x
else:
print " start recursion"
f(x+1)
print " end recursion"
print f(0)
start recursion
start recursion
start recursion
start recursion
start recursion
returning 5
end recursion
end recursion
end recursion
end recursion
end recursion
None
Do you see why the function returns None?
--
TZOTZIOY, I speak England very best.
"Dear Paul,
please stop spamming us."
The Corinthians
John Machin wrote:
# Doh! Looks like recursion not necessary. Google 'eliminate tail
recursion' :-)
I did, and found this: http://www.biglist.com/lists/dssslis.../msg00389.html
which explains that the Scheme compiler optimises (obvious) tail
recursion into iterative code. I'm wondering if the python compiler
does the same?
Iain This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Derek Rhodes |
last post by:
using
Python 2.3.4 (#53, May 25 2004, 21:17:02) on
win32
OK, I have a recursive function that should return a list, but doesn't
<start session>
def test(word):
if type(word) == str:
|
by: Steven Bethard |
last post by:
I have lists containing values that are all either True, False or None,
e.g.:
etc.
For a given list:
* If all values are None, the function should return None.
|
by: Sachin Garg |
last post by:
Hi,
When trying to return objects of type
std::list<MyClass>
from my function, I get a corrupt heap.
(I checked using MSVC++ 7.0 runtime heap check facility)
Basically, I am creating a local object
|
by: Fraser Ross |
last post by:
I need to know the syntax for writing a reference of an array. I haven't
seen it done often. I have a class with a member array and I want a member
function to return an reference to it. Returning a pointer to the first
element might do but I want to do what I've said.
Fraser.
|
by: Daisy |
last post by:
Let's say I've got a forum, where users can be moderators of each forum.
Tables look like this:
USER
--------
user_key
name
FORUM
| | |
by: agent-s |
last post by:
I have a function, generally described as so:
def function(args):
if condition:
if condition2:
function(args+1)
elif condition3:
print "text"
return True
else:
|
by: Joseph Geretz |
last post by:
I'm a bit puzzled by the current recommendation not to send Datasets or
Datatables between application tiers.
http://support.microsoft.com/kb/306134
http://msdn2.microsoft.com/en-us/library/ms996381.aspx
Formerly, with classic Microsoft DNA architecture, the ADO Recordset was a
primary transport medium, recommended for transmitting data between
application tiers. In fact, there are whole books written on the subject.
|
by: cyberdawg999 |
last post by:
Greetings all in ASP land
I have overcome one obstacle that took me 2 weeks to overcome and I
did it!!!!!
I am so elated!! thank you to all who invested their time and energy towards helping me with my problems.
Now for my new little problem,I had a problem posting the values from checkbox fields to a database and thats the obstacle I overcame.
Now the second part is my new problem is that I want that the next time that page loads for...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
| | |
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 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 a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
