STRNO - Editorial

editorial
, , , ,
2

Detailed solution for April Long Challenge.

5 Likes
3

#include <bits/stdc++.h>
using namespace std;
long long int k;
void prime_power_count(long long int n);
void sieveOfEratosthenes(long long int n,long long int s[]);
int main() {
long long int t,x;
scanf("%lli",&t);
while(t–){
scanf("%lli %lli",&x,&k);
prime_power_count(x);
}
return 0;
}
void prime_power_count(long long int n){
long long int s[n+1],signal=0;
sieveOfEratosthenes(n, s);
long long int curr=s[n];
long long int cnt=0;
while(n>1){
n=n/s[n];
cnt++;
curr=s[n];
if(cnt>=k){
signal=1;
break;}
}
if(signal==1)
printf(“1\n”);
else
printf(“0\n”);
}
void sieveOfEratosthenes(long long int N, long long int s[])
{
// Create a boolean array “prime[0…n]” and
// initialize all entries in it as false.
vector prime(N+1, false);

// Initializing smallest factor equal to 2 
// for all the even numbers 
for (long long int i=2; i<=N; i+=2) 
    s[i] = 2; 

// For odd numbers less then equal to n 
for (long long int i=3; i<=N; i+=2) 
{ 
    if (prime[i] == false) 
    { 
        // s(i) for a prime is the number itself 
        s[i] = i; 

        // For all multiples of current prime number 
        for (long long int j=i; j*i<=N; j+=2) 
        { 
            if (prime[i*j] == false) 
            { 
                prime[i*j] = true; 

                // i is the smallest prime factor for 
                // number "i*j". 
                s[i*j] = i; 
            } 
        } 
    } 
}

}
any ideas to optimize this code

4

You can refer to setter’s/editorial’s/tester’s solution all of them are optimized and easy to understand. Also you can look at the following simple code

for _ in range(int(raw_input())):
    x,k = map(int,raw_input().split())
    cnt = 0; i = 2
    while i*i <= x:
        while x%i==0:
            x //= i
            cnt += 1
        i += 1
    if x>1:
        cnt += 1

    if k<=cnt:
        print(1)
    else:
        print(0)
1 Like
5

Here are a couple of filters that can be added to get O(1) solution for certain cases:

  • For any given K; if X < 2K the result is always 0.
  • A direct result of this is, since X<=109; If k>=30, the result will always be 0 irrespective of the value of X.
2 Likes
6

My solution worked on my pc , but when i ran it on codechef, it printed out only 0s.
Can someone please help me?

Link to my code - CodeChef: Practical coding for everyone

Thanks.

1 Like
7

problem is here

if (check==0)
{
    check=1;
}

if(check>=k)        // use elseif
{
    cout<<"1"<<endl;
}
9

I had a solution if x is the no of total factors and k is the prime factors so we know that x will always have 1 as a factor and if(x-1>=k) then there will always exist a no example 2 x will be 2(1,2) and k will be 1 (2) and x = 3(1,7,49) and k will be 1(7) can anyone tell me what is wrong in this

10

My commented code for the solution.

11

@mlango you are right but can anyone figure out why my code passed only test case 1
see this:

12

For the setter’s solution(or tester’s solution also), can somebody explain why is he only counting prime factors till square root. Prime factorization can go even further than that, right?

Example 10000. Prime factorization goes even beyond 100, you will get primes even beyond that, so why is he only considering till square root?

13

i don’t think so. There are only two prime factors. 2 and 5. both are less than 100.
There is only one case when prime factors is > sqrt(n). When the number is prime itself.

2 Likes
14

Maybe I didn’t understand the solution correctly,then.As far as I know,we are getting prime factors of X,and if they are equal to or more then K,then answer is yes.
Now when we check for prime factors,we should try to get all of them,right?

Like 144 for example.The solution only checks till square root,12. But won’t we find any primes that divide 144 after the square root? Now in 144’s case,we won’t find any primes after 12 that divide 144. But what if a number exists like that? Or maybe I am forgetting some fundamental maths here.

1 Like
15

You will check for 2, Since 2 divides it, find how many time will it divide 144,

2^4 is the highest power of 2 which divides 144, count = 4
144/16 = 9 , check 3, 3^2 divides 9, count = 4+2 = 6
Now if 6>=k ans is yes otherwise No.

You can use for/while loop to check highest power which divides given number.

2 Likes
16

I understood that part bro. I am not getting why we won’t get prime factors for a number after the square root.It’s more of a mathematical question to me now.I couldn’t run this code in the challenge itself,just because of this reason.

17

If there is a factor beyond sqrt(n) then its power will be 1 ( n < (sqrt(n)+k)*(sqrt(n)+k) )
You can divide all factors less than sqrt(n) and what you will be left with is just a number>1 which itself is a prime factor.
For example lets take 14,
sqrt(14) = 3 ,
14/2 = 7
Now it doesn’t get divided by 3.
Check this : Efficient program to print all prime factors of a given number
Hence we can conclude that 7 is prime factor.

3 Likes
18

That along with the article made it clear.Thanks.

1 Like
19

what is the reasoning behind this logic? Fairly simple without finding prime factors !

20

this problem is all related to observation and nothing else.

21

which numbers we can directly say are not coprime without even thinking ? these are even numbers.

this is itself the solution dear.
And we have to print n/2 lines ofcourse because we have n/2 even numbers in the range of [ 1,n ], just prime 2 numbers in each line consecutively and in the case where n is odd print 3 numbers in the last or first line.

Thats it.

22

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