STRNO - Editorial

editorial
, , , ,
22

‘1’ is neither prime nor composite. Thus x>=k should be correct.

23

How about 26 ? The prime factors are 2 and 13. Square root of 26 is between 5 and 6. One of the prime factors is 13 which is greater than 6. The number 26 isn’t prime either.

24

read my next comment

25

What is the use of assert ? (Setter’s solution).

26
2 Likes
27

Can you elaborate your doubt please? Frankly I didn’t even read the editorial until your comment, whatever I referred is from the following proof(Smallest number with specific number of divisors - Mathematics Stack Exchange), the following proof gave me the hint :
image
By the above proof, what I have understood according to our given problem is :
For given number X we can get factors between 1 and n (where n is maximum number of divisors of X), if k<=n then print(1) else print(0)

Now can you please elaborate your doubt?

28

still doesnt work

30

i want to know why you have written
if x>1:
cnt+=1

please explain me this?

31 
while i*i <= x:
     while x%i==0:
         x //= i
         cnt += 1
     i += 1

Even after the above while block if still x value is greater than 1 means the final value of the x from the above block is a prime number, you can check with the simple TC for the given problem : Take X=2 and K=1.

Edit : After the while loop, still if x>1 then this can be a prime number and is a prime factor of the given value.

32

That is for the prime number case. Because the only number remaining after for and while loop can be a prime number.

33

I had to consider a lot of boundaries and approximations but logically it gave the right answer and my solution got AC.

Achieving the 1st sub-task was quite easy and doesn’t require that many boundaries, it was asked for K<=2.
So for any integer which is greater than 1 and is a prime number, has exactly 1 prime number and it’s X is 2( 1 and the prime itself). Talking about 2, as a result of the analysis, any integer greater than 1 and is not a prime number has at least 2 prime numbers as it’s factors.

and for the 2nd sub-task which had K>2, I had to use recursion which is explained in details

My Solution :- CodeChef: Practical coding for everyone

By the way thanks @taran_1407 for mentioning the concepts related to the problem this will surely help me out in a better way.

34 
if(x > 1) cnt++;

why this line again?

35

After the loop, still if x value is greater than 1 means the final value of the x is a prime number and it is a prime factor of a given original value.

You can check with the simple TC for the given problem : Take X=2 and K=1.

36

please help me what is wrong with my approach I am getting partially correct result, correct only for subtask 1.
My approach A = p1^a1.p2^a2…pk^ak where p1,p2…pk are k prime numbers and a1,a2,…ak are there frequencies.
Now ai >=1 for that prime number to exist in K prime numbers
Now X which is total number of factors of A, X = (a1+1).(a2+1)…(ak+1), now ai>=1,
So X >= 2^k.
Some edge case-
X can only attain a prime value if k is 1, else X is always a composite number.
Based on this approach here goes my solution.

`# include<bits/stdc++.h>

define int long long

using namespace std ;

int32_t main()
{
int t ; cin>>t ;
while(t–)
{
int x,k ; cin >> x >> k ;
bool isPrime = true ;
for(int i=2;i<=sqrt(x);i++)
{
if((x%i) == 0) { isPrime = false ; break; }
}
int minV = pow(2,k) ;
if((isPrime && k>1) || (x < minV)) cout << 0 << endl ;
else cout << 1 << endl ;
}
}`

Please tell me what am I missing.
Thanks In Advance

37

can you provide a code for the same i have tried so many ways

38

First, make a simple bool function that checks whether the given integer is prime.

bool prime(long long int n)
{
if(n%2==0)
{
return 0;
}
for(long long int i=3; i<=sqrt(n); i+=2)
{
if(n%i==0)
{
return 0;
}
}
return 1;
}

Then, create another function that counts no. of prime divisors using the previously defined bool function

long long int primeFactors(long long int n)
{
long long int count=0;
while(n%2==0)
{
count++;
n/=2;
}
for(long long int i=3; i<=sqrt(n); i=i+2)
{
if(n%i==0 && prime(i))
{
while(n%i==0)
{
count++;
n/=i;
}
}
}
if(n>2)
{
count++;
}
return count;
}

39

This part is incorrect. Think why.

40

I don’ t get this part at all. Can someone provide me with some invaluable insight?

42

where is your code

44

my bad i didn’t consider an edge case hehe… i wont waste ur time now.