1
$\begingroup$

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all the $k_i=1$. I am looking for fast solutions, heuristics are welcome. One can assume that primes upto $n$ are stored.

Edit: $p_1, p_2, ....p_n$ are any primes and not necessarily the first n primes.

$\endgroup$
7
  • 2
    $\begingroup$ This is usually referred to as $p_n$-primorial. It is written $p_n!!$ or $p_n\#.$ The numbers of this type are 2,6,30,210,... etc. $\endgroup$
    – daniel
    Dec 11, 2014 at 12:49
  • 1
    $\begingroup$ But I don't know what you mean when you say you are looking for solutions. $\endgroup$
    – daniel
    Dec 11, 2014 at 13:01
  • $\begingroup$ I presume they mean given a number $n$ test whether it is of that form. $\endgroup$
    – meta
    Dec 11, 2014 at 13:47
  • 1
    $\begingroup$ hmmm....so I suppose I am looking for a test for squarefree numbers. $\endgroup$
    – sudeepdino008
    Dec 11, 2014 at 15:58
  • 1
    $\begingroup$ No one has found a way to test numbers for squarefreeness that's any faster than factoring them. See, for example, mathoverflow.net/questions/16098/… $\endgroup$
    – Gerry Myerson
    Dec 12, 2014 at 9:14

1 Answer 1

Reset to default
1
$\begingroup$

You are looking for squarefree numbers. Unfortunately, as pointed out in the comments, no test faster than factoring has been developed to determine whether a number is squarefree.

$\endgroup$

You must log in to answer this question.

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