0
$\begingroup$

I'm solving algorithm problem. In this problem, there are max and min.

Between max and min, which number is not divided by square number? is problem.

When I solving this problem, many users solved using square numbers of a prime number.

But I don't understand why I can use square numbers of a prime number instead of normal square numbers.


EX) MAX = 10, MIN = 20

Normal square numbers = $10^2, 11^2 ... 20^2$

Prime square numbers = $11^2, 13^2 ... 19^2$

Users said that I can solve which numbers are not divided by square numbers using prime square numbers.


Can you explain why it can be?

$\endgroup$
3
  • $\begingroup$ Actually, from $10$ to $20$, you want to test which are not divisible by $2^2$, $3^2$ or $4^2$, since $5^2=25 >20$ is too high. But there is no need to test division by $4^2$ as it is a multiple of $2^2$, so you only need to test division by squares of those prime numbers less than or equal to the square root of the maximum $\endgroup$
    – Henry
    Commented Mar 28, 2018 at 10:45
  • $\begingroup$ @Henry I understand your saying. but it is not strict proof. $\endgroup$
    – haram
    Commented Mar 30, 2018 at 2:10
  • $\begingroup$ @haram Please remember that you can choose an answer among the given if the OP is solved, more details here meta.stackexchange.com/questions/5234/… $\endgroup$
    – user
    Commented Apr 1, 2018 at 8:23

2 Answers 2

0
$\begingroup$

HINT

By FTA $\forall n\in \mathbb{N}$ we have that $n=\prod p_i^{a_i}$.

$\endgroup$
2
  • $\begingroup$ I don't know that sign of right side. Can you explain more easily? $\endgroup$
    – haram
    Commented Mar 28, 2018 at 10:44
  • $\begingroup$ Take a look to the link en.wikipedia.org/wiki/… $\endgroup$
    – user
    Commented Mar 28, 2018 at 10:44
0
$\begingroup$

If $m^2|n$, take $p$ prime, $p|m$. Then $p^2|m^2$ and $p^2|n$.

$\endgroup$
2
  • $\begingroup$ Can you explain more easily? $\endgroup$
    – haram
    Commented Mar 30, 2018 at 2:13
  • $\begingroup$ @haram, every integer $m >1$ has a prime factor $p$ and the relation "... divides ..." is transitive. $\endgroup$ Commented Mar 30, 2018 at 14:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .