您的位置 首页 编程语言

A prime number is an integer that is divisible only by 1 and itself. A porcupine number is a prime number whose last digit is 9 and the next prime number that follows it also ends with the digit 9.

美国面试题4

1. 题目:

A prime number is an integer that is divisible only by 1 and itself. A porcupine number is a prime number whose last digit is 9 and the next prime number that follows it also ends with the digit 9.

 

2 .样例

For example 139 is a porcupine number because:
a. it is prime
b. it ends in a 9
c. The next prime number after it is 149 which also ends in 9. Note that 140, 141, 142, 143, 144, 145, 146, 147 and 148 are not prime so 149 is the next prime number after 139.
Write a method named findPorcupineNumber which takes an integer argument n and returns the first porcupine number that is greater than n. So findPorcupineNumber(0) would return 139 (because 139 happens to be the first porcupine number) and so would findPorcupineNumber(138). But findPorcupineNumber(139) would return 409 which is the second porcupine number.
The function signature is
int findPorcupineNumber(int n)
You may assume that a porcupine number greater than n exists.
You may assume that a function isPrime exists that returns 1 if its argument is prime, otherwise it returns 0. E.G., isPrime(7) returns 1 and isPrime(8) returns 0.
Hint: Use modulo base 10 arithmetic to get last digit of a number.

 

3. java 代码:

public class PorcupineNumber {
    public static void main(String[] args) {
        System.out.println();
        System.out.println(findPorcupineNumber(0));

    }
    public static int findPorcupineNumber(int a) {
        int i = ((a+1)/ 10) * 10 + 9;
        int num = 0;
        while (true) {
            // 9, 19, 29, 39 ....
            int start = i;
            int end = (i / 10 + 1) * 10 + 9;

            if ((isPrimeNumber(start) && isPrimeNumber(end))) { // 头尾是质数
                int count=0;
                for (int j = start + 1; j < end; j++) {

                    if (isPrimeNumber(j)) {
                    }else {
                        count++;
                    }
                    if(count==9){
                        return start;
                    }
                }
            }
            i = (i / 10 + 1) * 10 + 9; // 进位10

        }

    }



    //判断一个数是否为素数
    public static boolean isPrimeNumber(int num){

        if(num == 2){
            return true;// 对2单独处理
        }
        if(num < 2 || num % 2 == 0){
            return false; // 识别小于2的数和偶数
        }
        for (int i =3; i<=Math.sqrt(num);i+=2){
            if(num % i == 0){  // 识别被奇数整除
                return false;
            }
        }
        return true;
    }

}

 

 

如有问题,可扫描公众号留言

关于花猫大叔短视频创业 作者: hadoopall

热门文章

发表评论

电子邮件地址不会被公开。