Python(Simple math codes)

This is a place to discuss python. Here are two codes I made to find out the prime factors.

#NAME: Prime Factors 1 aka First
n = int(input('Enter the number whose factors you need to know: '))
i = 2
while (n != 1):
    if (n%i == 0):
        print(i, n//i)
        n //= i
    i += 1
    if (i>n):
        i = 2

#NAME: Prime Factors 2 aka Second
n = int(input('Enter the number whose factors you need to know: '))
for i in range(2,n):
    if(n%i == 0):
        print(i, n//i)
        n//=i

These may not be the best but are quite efficient. Share your code in the comments.

Also, make a program to find the HCF of two numbers(it probably requires the use of lists and I don't know much about lists).

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

program to find the HCF of two numbers can be made using Euclid's algorithm

Zakir Husain - 2 months ago

It doesn't requires list but rather it requires recursion

Zakir Husain - 2 months ago

I've done it. A program to find the HCF of two numbers. It uses Euclid's Division Algorithm which is the same as finding the HCF using the long division method.

#NAME: HCF
r = 1
a = int(input('Enter the smaller number'))
b = int(input('Enter the bigger number'))
while (r>0):
    r = b%a
    b = a
    a = r
print(b)

Aditya Mittal - 2 months ago

You only need to check for factors upto $\sqrt{n}$ the factors over that are just $\frac{n}{\text{already known factors}}$ , this can increase efficiency by quite a lot

Jason Gomez - 2 months ago

But $\sqrt{n}$ is float for most of the integers 'n' and the range loop is not accepting floats.

I reduced it to half by doing

1	`for i in range(2,n//2+1):`

Aditya Mittal - 2 months ago

Try this instead

1	`for i in range(2,int(n**0.5+1)):`

Jason Gomez - 1 month, 4 weeks ago

@Jason Gomez – yes it works!

Aditya Mittal - 1 month, 4 weeks ago

Yeah. Try

for(n=2;n*n<=i,n++)
{
    Code
}

Jeff Giff - 2 months ago

I don't understand what you want to say

Aditya Mittal - 2 months ago

You need only check for numbers up to $\sqrt{n}$ !

Jeff Giff - 1 month, 4 weeks ago

can you(anyone) suggest anything so that it does powers easily. Like I tried $5^{10} = 9765625$ in both the prime factor programs and the output was

Enter the number whose factors you need to know: 9765625
5 1953125
25 78125
125 625
625 1

Aditya Mittal - 1 month, 4 weeks ago

Check out this code, gives all prime factors and their multiplicity too

n=int(input())
i=2
prime=[]
while i<=n**0.5:
    while n%i==0:
        prime.append(i)
        n/=i
    i+=1
if n!=1:
    prime.append(n)
print(prime)

Jason Gomez - 1 month, 4 weeks ago

It is good. I added this at the last in place of print(prime) to print each factor in a separate line

1 2	`for n in prime: print(n)`

Aditya Mittal - 1 month, 4 weeks ago

@Jason Gomez Is there any function in python which finds the common items in two or more lists?

Aditya Mittal - 1 month, 4 weeks ago

Yes you can just use set conversion of both lists and then use intersection method to do so.

1
2
3

list1 = [3,4,5]
list2 = [3, 5, 7, 9]
list(set(list1).intersection(list2))

1	`Output : [3,5]`