Beginner Python - better way to write this?

  • Comp Sci
  • Thread starter zeion
  • Start date
  • #1
467
0
Hi,

This compiles, I just wanted suggestions for fewer lines. Thanks.



Homework Statement



Need to write a function for this:

Given an int variable, return a factor of that int. If the input is not between 0 and 100 return -1. If there are more than one distinct factors, return the second smallest. 1 does not count as a factor.

Homework Equations





The Attempt at a Solution



def find_factor(x):
if x > 1 and x < 100: 'Checks if x is in the range'
for a in range(2, x+1): "1 doesn't count, so skip it and we need to get up to x itself for the primes"
if x%a==0: 'Check if it is a factor'
return a
elif x == 1: 'Special case for 1'
return 1

else:
return -1 'For out of range'
 

Answers and Replies

  • #2
85
1
I may be seeing it wrong (I don't know python), but it doesn't seem like you're returning the second smallest in the case of two or more distinct factors. You fire off a return immediately after finding the smallest distinct factor.
 
  • #3
32
0
I may be seeing it wrong (I don't know python), but it doesn't seem like you're returning the second smallest in the case of two or more distinct factors. You fire off a return immediately after finding the smallest distinct factor.
I think that's true. Also, zeion you should post codes using code tags, this is rather important since Python's scopes depends on scopes emphasized by indents. (correct me if i'm wrong)
 
  • #4
467
0
How do I indent?
I indented on the post but it doesn't show.
 
  • #5
32
0
Use code tags =) [*CODE] code is written here, indents will be shown [/CODE*] use it without the *.
 
  • #6
467
0
Ok I revised it:

Code:
def find_factor(x):

    if x > 1 and x < 100: 'Checks the range of input'
        for a in range(2, x + 1): 'Checks the smallest factor > 1'
            if x % a == 0:
                for b in range(a + 1, x + 1): 'Checks for second smallest factor'
                    if x % b == 0:
                        return b 'Returns second smallest factor'
                return a 'Returns first factor if there is nothing greater'
    elif x == 1: 'Special case for 1'
        return 1
    else:
        return -1 'For out of bound input'
 
  • #7
32
0
This probably should work the way you write it (i guess?) but for efficiency, you can do something like this.
Code:
bool = 0; 'this variable is to check whether a factor is found before or not'
for a in range(2, x + 1):
	if x % a == 0:
		if bool == 1:
			return a
		else
			bool = 1
return a 'Returns first and only factor of x'
There might be syntax errors, and i don't know if it would work but nested for and if loops create confusion, i'd avoid it like this. Hope it helps.
 
  • #8
Borek
Mentor
28,568
3,021
Why range(2,x+1)?
 
  • #9
467
0
Why range(2,x+1)?
Because 1 doesn't count as a factor and the range function stops at 1 before the limit, so if I used x it would not actually check x itself, which it needs to if the input is prime.
 
  • #10
Borek
Mentor
28,568
3,021
So you are telling me you need to check if 100 is not divisible by 99?
 
  • #11
467
0
So you are telling me you need to check if 100 is not divisible by 99?
No because the check would stop at 5.
If input is 7 and range stops at 7, it would check 2 to 6, not returning any factors.
 
  • #12
32
0
Why range(2,x+1)?
It has to do with the definition of the range function in python

for example range(1,10) means a vector of numbers
1,2,3,4,5,6,7,8,9

I agree that the definition is confusing =)
 
  • #13
Borek
Mentor
28,568
3,021
I know how range works. You are both still missing what I am aiming at.

Think about performance.

97 is a prime number. If you know it wasn't divisible by anything smaller than 10, do you have to check every number larger than 10?
 
  • #14
32
0
Hmm, i got your point. Well, you are right. If it doesn't find any factor until it reaches x/2 he won't find any other after so the program returns the x value itself. That can make it more efficient right? Correct me if i am wrong, it was a straightforward thought.
 
  • #15
Borek
Mentor
28,568
3,021
x/2? Try harder :wink:
 
  • #16
85
1
x/2? Try harder :wink:
Are you saying that for x/2 to be a factor, so too must two? Your power is maximum, Borek.
 
  • #17
32
0
x/2? Try harder :wink:
Well yeah, since x/2 won't be a "prime factor" why should i consider it since i am not looking at all the divisors of x in range(1,x+1) (silly me :) ) So the range should be up to sqrt(n) right?
 
  • #18
Borek
Mentor
28,568
3,021
So the range should be up to sqrt(n) right?
Exactly.

This can be a little bit tricky in your case, as for example for 34 you should return 17 (second lowest factor), which is higher than [itex]\sqrt {34}[/itex]. This will require additional coding and may be not worth effort for numbers lower than 100 (actually the fastest way in this case is to store all possible answers in table and to not calculate anything, just return ready number). Still, it is always worth to remember about code efficiency.
 
  • #19
467
0
Exactly.

This can be a little bit tricky in your case, as for example for 34 you should return 17 (second lowest factor), which is higher than [itex]\sqrt {34}[/itex]. This will require additional coding and may be not worth effort for numbers lower than 100
Great. So all that you've said is redundant and beyond the point of this question.

Still, it is always worth to remember about code efficiency.
How is my code inefficient? It does not check 99 numbers if the input is 99. The code finishes as soon as the second factor is found.
 
  • #20
Borek
Mentor
28,568
3,021
How is my code inefficient? It does not check 99 numbers if the input is 99. The code finishes as soon as the second factor is found.
How many checks do you do if the input is 97? After 10 divisions it is obvious there will be no two factors, but you do 87 more.
 
  • #21
32
0
zeion said:
How is my code inefficient? It does not check 99 numbers if the input is 99. The code finishes as soon as the second factor is found.
What if a prime number close to 100 is entered? It does a calculation for all of the numbers up to that number to figure out that there is no factors of it besides itself.
 
  • #22
467
0
Okay fine. But I don't see how changing the maximum range to sqrt(x) does anything to solve this. It would not even get to x itself.

Maybe I should write another function to check if x is a prime to begin with?
 
  • #23
32
0
Nope you don't have to, if the number doesn't have any factors, then it is prime. This method itself checking whether the number is prime or not. You just return the number if it doesn't find any factors up to sqrt(x).
But i think you should consider the "trickyness" of the sqrt(x) as Borek mentioned. Do you really need that code to be really efficient? I think you can just define range to x/2, assuming that today's computers are fast enough to handle only that much of process less than a second =)
 
  • #24
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
This compiles, I just wanted suggestions for fewer lines.
I just wanted to point out that fewer lines is not necessarily better. In fact, the opposite is often true.

When writing in python, probably the most important thing is simple-to-write, easy-to-read code. Your code in post #6 is probably the most literal translation of the most straightforward algorithm.

On an unrelated note, I'm going to take this moment to tease Borek for optimizing prematurely. :wink: Until you actually find yourself in a situation where speed matters, the only value in his optimization is as an exercise in optimization. (of course, such an exercise could be quite valuable for you to work through...)
 
  • #25
Borek
Mentor
28,568
3,021
On an unrelated note, I'm going to take this moment to tease Borek for optimizing prematurely. :wink:
As I wrote above - it is not necessarily important in this case.

However, I see a giant difference between code written by oldtimers (like me) and those who came to programming much later. Those that started one the early microcomputers value resources much more, newcomers have a tendency to write bloated code that uses huge amount of memory and processor speed to do simple tasks. I was talking about it few years ago with one of those programmers and he said something between the lines "That's not a problem, we can buy faster computer". For me that's idiocy.

I don't mean code has to be always compacted and optimized to the smallest bit, but whenever you write something you should at least be aware where such optimizations are possible, and whenever you are faced with several possible solutions to the problem you should select the one that is not only easy to code, but also fast and easy on memory. If you don't train yourself on seeing these things from the beginning, you will need megabytes for "Hello world!".
 

Related Threads on Beginner Python - better way to write this?

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
3
Views
1K
Replies
3
Views
2K
Replies
1
Views
5K
Replies
3
Views
1K
Replies
1
Views
4K
Replies
1
Views
728
Replies
3
Views
1K
Top