CHFJB – Editorial

PROBLEM LINK:

Practice
Contest

Author: Arkapravo Ghosh
Tester: Aparup Ghosh
Editorialist: Aparup Ghosh

DIFFICULTY:

EASY

PREREQUISITES:

Primality test, factorization

PROBLEM:

Given a positive integer N, you need to find the number of factors of N except 1 and itself. If N is a prime number then simply output -1.

QUICK EXPLANATION:

We can find the number of factors of N except 1 and itself by iterating from 2 upto sqrt(N). If the no of factors in zero(0), then output -1(i.e. N is a prime) otherwise output the number of factors.

EXPLANATION:

According to the given problem we need to find the number of factors of N except 1 and itself, as it is mentioned that the job cannot be performed in 1 day(according to the instructions) or N days(as Chef will leave). So we iterate from 2 to sqrt(N) and keep a count of the number of factors of N. The idea of iterating from 2 to sqrt(N) is simple, you can identify it with a simple observation. For every number (< sqrt(N) ) which is a factor of N, there is another number(> sqrt(N) ) which is a factor of N too. So for every number(< sqrt(N) ), if it is a factor of N, we increase the count by 2. If the factor is equal to sqrt(N) (in case N is perfect square), then we increase the count by 1.
After counting the number of factors of N, if the count is equal to 0(i.e. N is prime), we print -1, else we print the number of factors of N. You can find the solutions below.

AUTHOR’S AND EDITORIALIST’S SOLUTIONS:

Author’s solution can be found here.
Editorialist’s solution can be found here.

2 Likes

@aparup_ghosh also provide the link of this editorial in the contest page :slight_smile:

@happypotter0 I will do it soon. :slight_smile:

2 Likes

Will you be re-judging the competition entries (for the ~20 who got WA without AC) excluding the out-of-range test value of N=1?

import java.util.*;
class factors
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,no,c=0;
System.out.print("enter the number ");
n=sc.nextInt();
for(int i=2;i<n;i++)
{
if((n % i)==0)
{
c=c+1;
}
}
if(c==0)
System.out.println(“1”);
else
System.out.println©;

}
}

Please wikify the editorials especially if your college friends are to upvote them. Gaining karma by official editorials (of contest you hosted) is not allowed by regulations as you get its reward separately.