top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Illegal prime numbers

+2 votes
980 views

it is illegal to share some certain prime numbers in US and if you do so,you will get arrested.Follow this link to get more details :

My question is : it is very easy to find multiplication of two prime numbers but tough to get what are the prime numbers which multiplication results this number . Example : 7*11= 77 but you are given 77 = ? * ? where ?= two prime numbers only (ans = 7 and 11).Another example : 11*13= 143 but you need to solve it for 143 and you output : 11 13
So I need a program ,efficient one, to get solutions to such type of mathematical problem.
Adding more examples:
input:1. 21 -> 3,7
2. 189 -> 3,7,9
3.1363 -> 29,47 .... and if is not possible then print -1 example 1. 4 and its factors 2*2 where 2 is repeated so print -1
2. 9-> -1
3. 24->-1 ( prime factors are 2^3 * 3= 8*3 where 8 is not prime so print -1).
Thanks in advance.

posted Jul 5, 2016 by Shivam Kumar Pandey

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+5 votes
 
Best answer

This is an interesting topic!

To check if a number is prime number, we have to divide it with all the numerical values between 2 and the number it self and check for reminder.

Typical implementation,

boolean isPrimeNumber(long number) {
    for(int i=2; i<number; i++) {
        if(number % i == 0)
            return false;
    }
    return true;
}

Possible optimizations....
- We don't have to iterate more than half of the number while even, you know if the value is more than half then multiplying it by two will lead to more than what we want.
- We don't have to iterate more than 1/3rd of the number while odd, assuming to be divisible by 3.
Optimized implementation,

static boolean isPrimeNumber(float number) {
    float iterateTill = 0;
    if(number%1 != 0) {
        return false;
    }
    if (number%2 == 0) {
         iterateTill = number/2;
    }
    else {
         iterateTill = number/3;
    }
    for(int i=2; i<=iterateTill; i++) {
        if(number % i == 0)
            return false;
    }
    return true;
}

I will think over this and if I find any better solution, I will post it.

Hope this helps!

Update 1:

Sorry for not understanding the question thoroughly! This method prints the result you seek. Assuming there could be more than 2 prime numbers multiplied in the provided number. I will refine the code further....

static boolean getPrimeNumbersWithin(long number) {
    long firstNumber = 2;
    long secondNumber = 2;
    float remainingNumber = number;

    while(remainingNumber > 0 && firstNumber < number) {
        remainingNumber = (float)number/(float)firstNumber;
        if(isWholeNumber(remainingNumber)) {
            if(isPrimeNumber(remainingNumber)) {
                secondNumber = (long)remainingNumber;
                remainingNumber = 0;
                break;
            }
            else {
                // try if this could be acheived with more numbers
                if (getPrimeNumbersWithin((long)remainingNumber)) {
                    secondNumber = 0;
                    remainingNumber = 0;
                    break;
                }
            }
        }
        do {
            firstNumber++;
        }
        while(!isPrimeNumber(firstNumber));
    }
    if(remainingNumber == 0) {
        System.out.println(firstNumber);
        if(secondNumber != 0){
            System.out.println(secondNumber);
        }
        return true;
    }
    else {
        System.out.println("No match");
        return false;
    }
}

static boolean isWholeNumber(float number) {
    if(number%1 != 0) {
        return false;
    }
    return true;
}

Test run result,

getPrimeNumbersWithin(6090); // Results 7 29 5 3 2

online link for your immediate reference.

answer Jul 6, 2016 by Vinod Kumar K V
I think checking till SQRT(n) should be fine...
But the problem is not to check if number is prime or not, but to find out the prime factors of a number. Do you like to correct your solution?
Hi Vinod,your solution isn't according to problem.
Adding more examples:
input:1. 21 -> 3,7
2. 189 -> 3,7,9
3.1363 -> 29,47 .... and if is not possible then print -1 example 1. 4 and its factors 2*2 where 2*2=4 is is not prime so print -1
2. 9-> -1
3. 24->-1 ( prime factors are 2^3 * 3= 8*3 where 8 is not prime so print -1).
Oh! Sorry, my bad. I will update my answer.
ok @Vinod
Thanks Vinod, I just checked the solution with various inputs like 144: 3 3 2 2 2 2( it should be -1 only ) but it doesn't matter as we are getting good results for other inputs like 10010 ...etc. gave you +1
Thank you @Shivam
Similar Questions
+6 votes

First see this example: let you have a number 8 which is divisible by 4 which is square of 2 and 27 which is divisible by 9 which is square of 3.I need a solution for numbers input from 1 to 10^18.hope for efficient program written in any programming language.
Thanks in advance.

+4 votes

Requirements:

1.No input should be processed, and the output should be in the form of 2 3 5 7 11 13 ... etc.
2. No reserved words in the language are used at all
3.The language should at least allow structured programming, and have reserved words (otherwise point 2 would be moot).

+2 votes

How to find prime numbers between given intervals? Sample code along with the complexity would be helpful?

+3 votes

A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1.
All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.

Given a positive number x, print all Jumping Numbers smaller than or equal to x. The numbers can be printed in any order.

Example:

Input: x = 20
Output: 0 1 2 3 4 5 6 7 8 9 10 12

Input: x = 105
Output: 0 1 2 3 4 5 6 7 8 9 10 12
21 23 32 34 43 45 54 56 65
67 76 78 87 89 98 101

Note: Order of output doesn't matter,
i,e., numbers can be printed in any order

0 votes

Which is the best practice for variable declaration within the function ? Or is it vary from one language to other one ?

...