wicked lily
def factors(value):
factor = []
while value >1:
if value == 1:
factor.append(1)
break
elif value % 2 == 0:
value = value//2
factor.append(2)
elif value%3 == 0:
value = value//3
factor.append(3)
else:
factor.append(value)
break
return factor
so the issue is for large prime numbers it will just return the value
granite nebula
spiral sentinelBOT
Increase your chance of getting help and look like a pro by sharing codeblocks not images. For example, you can type the following. Note, the ``` must be on their own line.
```
for number in range(10):
total += number;
```
Discord will render that as so:
for number in range(10):
total += number;
Click here to learn more about codeblocks: https://exercism.org/docs/community/being-a-good-community-member/writing-support-requests and http://bit.ly/howto-ask
wicked lily
def factors(value):
factor = []
if value == 1:
factor.append(1)
for i in range(2,value+1):
while value % i == 0:
factor.append(i)
value = value//i
return factor
i have used anouther method which is correct with compiller but when i run test it is too slow in exercism
granite nebula
You need backticks ` for codeblocks, not quotes '
Does your for loop need to always go all the way to value + 1?
What if value is 2 ^ 1024?
wicked lily
as if ther number is like too large 123456 then it has only one factor that is itself
granite nebula
as if ther number is like too large 123456 then it has only one factor that is i...
But what if it's not?
floral dew
I don't think you understand correctly what's Isaac is saying here.
He was trying to guide you toward reducing the search space.
You made the comment that
if ther number is like too large 123456 then it has only one factor that is itself
which is not always true, questioned by Isaac.
Posting the test case (please use codeblock and not picture) just further proving his point, that very big number there clearly has 11 as another factor and not just itself.
wicked lily
def factors(value):
factor = []
if value == 1:
factor.append(1)
for i in range(2,1000):
while value % i == 0:
factor.append(i)
value = value//i
return factor
so here i am reducing the search space which is getting true for 10 test cases but still for very large number
it is still giving error
floral dew
Yeah, you are technically reducing the search space but not in the correct way
Let take the number 100 for example
would you mind list out all the possible factors of it?
wicked lily
1,2,4,5,10,20,25,50,100
floral dew
right. did you notice something about factors after 10?
wicked lily
it rise almost twice times
floral dew
let me be a bit more specific, what are the relationship between factors before 10 and after 10
wicked lily
don't able to decode
floral dew
1 * 100 = 100
2 * 50 = 100
see the pattern?
floral dew
im not sure what that formula is about
but you can observe the same thing here
now look at factors of 36
1,2,3,4,6,9,12,18,36
wicked lily
so i should decrese the search like sqaure root of value
floral dew
correct
wicked lily
def factors(value):
factor = []
if value == 1:
return factor
for i in range(2,3*int(value**0.5)):
while value % i == 0:
factor.append(i)
value = value//i
return factor
this code runs perfecly
but the number is some large that if i only do that 1*int(value**0.5) it still gave error
this complexity is the theta of root n and the previous one was the theta of n^2 that's why there is so much difference in time. Am I correct??
floral dew
no idea. im not even sure what problem is this, i just wanted to chime in about the search space
the title doesnt seems to give a lot of infomation about which exercise this is
wicked lily
prime_factors
granite nebula
but the number is some large that if i only do that 1*int(value**0.5) it still g...
Once you get to sqrt(val), do you need to search any more numbers?
granite nebula
this complexity is the theta of root n and the previous one was the theta of n^2...
Yes. O(sqrt(n)) (or theta(sqrt(n))) is much smaller than O(n) (or theta(n)). Consider if n is 1,000,000. One requires 1 thousand tests. The other requires 1 million tests. If each operation is 0.1 seconds, that's the difference between 1.5 minutes and over a day.