×

# SMALLSQ - Editorial

Practice

Contest

Author: Akshay Venkataramani

Tester: Timothy

EASY-MEDIUM

# PREREQUISITES:

Math, Sieve of Eratosthenes, Prime Factorization

# EXPLANATION:

Let's look at the solution using an example. Suppose the input is 60. The prime factorization is:

60 = 22 * 3 * 5

Looking at this might've given you a hint to the solution. The factors in the prime factorization of a square number have even powers. Hence, we just need to find the factors that have odd powers.

3 and 5 are the factors that have odd powers in the prime factorization of 60. Multiplying 60 by 15 (3*5) gives 900, which is a square number whose prime factorization is:

900 = 22 * 32 * 52

To find the prime factorization of a number, we slightly modify the Sieve of Eratosthenes to calculate and store the smallest prime factor for all numbers. This precalculation allows us to find the prime factorization extremely fast. The following routine is used to find the prime factorization:

map<ll,ll> factors;
while(n!=1)
{
factors[smallestPrime[n]]++;
n=n/smallestPrime[n];
}
return factors;


# AUTHOR'S AND TESTER'S SOLUTION:

Author's solution can be found here.

Tester's solution can be found here.

This question is marked "community wiki".

52
accept rate: 0%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,722
×303
×36
×29

question asked: 21 Jan '18, 17:32

question was seen: 267 times

last updated: 05 Feb '18, 13:57