Kiwox Interview Question Software Engineer / Developers
Team: Kiwox
Country: Chile
Interview Type: In-Person
@Rakesh..you r technically correct, but there is one problem..it is not min time complexity..you are actually iterating the loop for n/2 time...that is also not required..suppose there is another number m, m< n/2
n / (n/2) = 2 and n / m = x (say, since m< n/2), then x > 2 (say 3 or 3.33)
waht I feel is that you dont need to check till n/2, you can check upto m....because if there exists any number m < y < n/2, for which n%y=0 then (n /m) < (n / y) < 2....now if n/y=z, then n is also divisible by z....and while iterating upto m, you have already checked z....thus if n is not divisible by z then it is also not divisible by y....this logic is applicable for other numbers also...but i am not sure what is the minimal limit upto which we must check...
int isPrime(int num){
int i = 2;
if(num <= 1) return 0;
do{
if( num%i == 0) return 0;
i++;
} while(i*i <= num)
return 1;
}
You can use += 2 instead of ++ if you first test if num % 2 is 0
boolean isPrime(int num) {
if(num <= 1 || num % 2 == 0) {
return false;
}
for(int i = 3; i * i <= num; i += 2) {
if(num % i == 0) {
return false;
}
}
return true;
}
we can improve as below:
int isPrime(int num){
int i = 1;
if(num <= 1) return 0;
if(num == 2 || num == 3) return 1;
/* primes will be of 6k + or - 1 form */
if((num - 1)%6 != 0 && (num + 1)%6 != 0) return 0;
for(; i*i <= num; i += 2){
if( num%i == 0) return 0;
}
return 1;
}
#include <stdio.h>
#include <math.h>
int main()
{
int isprime(int num);
unsigned int n;
printf("enter positive integer : ");
scanf("%d",&n);
isprime(n)?printf("%d is prime\n",n):printf("%d is not prime\n",n);
return(0);
}
int isprime(int num)
{
if(num==0 || num==1)
return(0);
else
{
int i;
for(i=2;i<=((int)sqrt(num));i++)
{
if(num%i == 0)
return(0);
}
}
return(1);
}
public class prime {
- Rakesh April 03, 2013/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int i=21;
int flag=0;
for(int j=2;j<=i/2;j++)
{
if(i%j==0)
{
System.out.println("not prime");
flag=1;
break;
}
}
if(flag!=1) System.out.println("prime");
}
}