Codenation Republic Hiring challenge

31

easy one just make a function isprime which as name suggests returns true if a number is prime else false

like isprime(7) = true
isprime(10) false

now decompose a number in its canonical form
100 = 2^2 * 5^2

if the number of primes in canonical form is more than 1 print(NO)

solution
if n==1:
print(“No”)
if n==2:
print(“YES”)

else:
canonical_form = get_canonical(n)
if len(canonical_form) > 1:
print(NO)
else if isprime(canonical_form prime’s power + 1):
print(“YES”)
else:
print(“NO”)

32

Hey thanks but Can you explain me why “number of primes in canonical form is more than 1 print(NO)” i dont get that.

33

Given a number of the form P_{1}^{a}.P_{2}^{b}..., then what are the total factors? By using basic combinatorics it is (a+1).(b+1)... So, If the canonical form has more than 2 primes, then total number of factors is definately not a prime because it has atleast two factors which are not 1 or the number itself. However, if there is only one prime in the canonical form you have to put an additional prime check on a+1.

2 Likes
34

Oh okay wowww really great explanation man Thanks alot! Also did u do the 3 question?

1 Like
35

However, I think this question can be solved using a slightly simple approach. You can count the total number of factors of a number in sqrt(N). Then check if this number is a prime, build a Linear Sieve in the pre-processing step.

1 Like
36

Nah. I didn’t appear for the test besides I am a Noob in CP. :slight_smile:

1 Like
37

I did that thats why it was giving WA idk

1 Like
38

You need to find all the factors of N in sqrt(N) time… put it in an array… then find the length of the array and print if the length is prime or not

39

How did you find the P for it ?

40

I did that too but idk WA :(((

41

I guess it’s the flow error… send the code if you have. I got AC for what I said above :smiley:

42

Brother can you plz share the code?

43

Did you solve the 4th ques???

44

can you share the code for the 4th ques???

45

I did this with the same approach.

46

Yes

47

4th Question: 7rADZX - Online C++0x Compiler & Debugging Tool - Ideone.com

49

But (1/i) only denote the winning of ith position.how can we get the expected value for the number of position to win?

50

bro can you tell me your approach :innocent:

51

Can you please explain your approach?