Tutorial Writeup - Prime Factors

[wingkwong]

Markdown Path: tutorials/math/prime-factors.md

• Overview
• Explanation with 1 ~ 2 LC problems
• Suggested Problems (See arrays.md as a reference for the format)

You can include other info related to this topic as you wish.

[abhishek-sultaniya]

Hello @wingkwong ,I would like to work on this issue.It would be great if you will assign me this.

[wingkwong]

Assigned. Feel free to discuss with me in Discord.

[UjjwalAggarwal-1]

so is it under process or may i take it up? under hacktoberfest, that is

[wingkwong]

@abhishek-sultaniya Any update?

[abhishek-sultaniya]

@abhishek-sultaniya Any update?

Sorry,I am not able to complete it on time.Little busy due to some other works .Please assign it to @UjjwalAggarwal-1

[wingkwong]

@UjjwalAggarwal-1 Assigned. Please look at CONTRIBUTING.md first.

[wingkwong]

Unassigned due to inactivity.

[charann29]

If there isn't anyone currently assigned to this task, I'd like to take it on. Kindly assign this issue to me, @wingkwong

[wingkwong]

@charann29 Assigned. Please look at CONTRIBUTING.md first.

[Ishwarendra]

If no one is working, I can take up this issue. I have following things in mind

1. How to find prime factors naively in $n \cdot log(n)$ time and then optimising it to $\sqrt{n}$.
2. Basic idea about why number of prime factors cannot exceed $log(n)$.
3. Special case where numbers are small $< 10^7$. We can first use sieve to find min_prime[i] = smallest prime factor of i for each $i \in [2, n]$.

Problem List:

1. 2521. Distinct Prime Factors Product of Array
2. 2507. Smallest Value After Replacing with Sum of Prime Factors
3. 952. Largest Component Size by Common Factor

Practice Problem:

1. 263. Ugly Number
2. 650. 2 Keys Keyboard
3. 1627. Graph Connectivity with threshold
4. 2709. Greatest Common Divisor Traversal

[wingkwong]

reassigned to @Ishwarendra due to inactivity.