[每日一道小算法（七十五）] [素数] 最近邻的素数

短命女 2023-07-10 14:05 4阅读 0赞

前言：  
今天参加了一个公司的笔试，关于素数的，所以在这里贴一下。

### 题目描述 ###

输入大小n的正整数数组arr\[\]，arr\[\]的每个元素a取值范围为：1<=a<=100000，找到与每个元素相邻最近的一个素数并作为新的数组返回。请设计时间复杂度较优的算法，并给出时间与空间复杂度分析。  
输入：  
5  
1  
2  
3  
8  
10  
输出：  
2  
2  
3  
7  
11

### 解题思路 ###

这道题，我也没想到最优解题思路。完全使用暴力破解法完成的。对输入的整数两边分别查找素数。也就使用两个指针分别向两边查找。第一个找到的就是离着最近的一个素数。反正这种是最暴力的方法。我也没想到最好的，在这里贴一下，有大神想出最好的可以在这里贴一下。相互学习。

### 代码样例 ###

package AiStudy;
    
    
    import java.util.ArrayList;
    import java.util.Scanner;
    
    /** * @note 最近邻素数 * 输入大小n的正整数数组arr[]，arr[]的每个元素a取值范围为：1<=a<=100000， * 找到与每个元素相邻最近的一个素数并作为新的数组返回。请设计时间复杂度较优的算法，并给出时间与空间复杂度分析。 * <p> * 第一行输入n，表示需要输入n个正整数， * 然后输入n个正整数a，1<=a<=100000 * <p> * 对于每组测试数据，输出n行最近邻的素数，行末无多余空格 */
    public class Main { 
    
        private static int makeNearestPrime(int a) { 
            if(a<=2)
            { 
                return 2;
            }
            if(a==3)
            { 
                return 3;
            }
            int left = 0;
            int right = 0;
            int j;
            int i;
            for ( i = 1; i <a-2 ; i++) { 
                for ( j= 2; j <= Math.sqrt(a+i); j++) { 
                    if((a+i)%j==0)
                    { 
                        break;
                    }
                }
                if(j>Math.sqrt(a+i))
                { 
                    left=1;
                }
                for (j=2; j <=Math.sqrt(a-i) ; j++) { 
                    if((a-i)%j==0)
                    { 
                        break;
                    }
                }
                if(j>Math.sqrt(a-i))
                { 
                    right=1;
                }
                if(left==1||right==1)
                { 
                    break;
                }
            }
            if(left==1)
            { 
                return a+i;
            }else { 
                return a-i;
            }
    
        }
        public static ArrayList<Integer> list = new ArrayList<Integer>();
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) { 
                int n = in.nextInt();
                int len = n;
                while (n-- > 0) { 
                    int a = in.nextInt();
                    // 求最近素数
                    int res = makeNearestPrime(a);
                    list.add(res);
                }
                for (int i = 0; i < len; i++) { 
                    System.out.println(list.get(i));
                }
            }
        }
    }