首页 > 代码库 > 判断一个数是否是素数

判断一个数是否是素数

2024-08-01 22:50:35   218人阅读

一、判断一个数是否是素数
        思想：拿比自己小的整数依次进行比较
        
    public String isSu(int a){
        for(int i = 2 ; i<a; i++) {
            if(a%i == 0){
                return "不是";
            }
        }
        return "是";
   }
    //算法改进；只要小于该数字的二次根就可以了，因为大于该数字的二次根的数字也是不能整除的
   
    public String isSu(int a){
        for(int i = 2 ; i<Math.sqrt(a); i++) {
            if(a%i == 0){
                return "不是";
            }
        }
        return "是";
   }  

二、实现一个冒泡排序的算法
        //思想：依次比较相邻两个数的大小，大数放在后面，小数放在前面，直至比较最后两个数，将小数放在前面，大数放在后面，重复以上过程
    public void sort(int []array){
        for(int i=0;i<array.length;i++){
            for (int j=0;j<array.length-i-1;j++){
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
        }
    }
     平均时间复杂度为O(n2) 最好时间复杂度为O(n)
三、插入排序算法（用于少量数据时候）
        //思想：在一个已经排序好的序列中插入一个数据
    private static int[] insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            for (int j = i - 1; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
        return array;
    }
     平均时间复杂度为O(n2) 最好时间复杂度为O(n)
四、快速插入排序（效率较高）
        快速排序思想：
    一趟快速排序是：
1，随机产生一数列，选取第一个数（这里也可选其他的数）作为比较的基石，假设这个数为X,这样X=A[0]；设两个变量i=0，j=n-1；n是这个数列的长度
2，从前面开始找，找到第一个比A[0]大的数，找到了就与X交换
3，从后面开始找，找到第一个比A[0]小的数，找到了就与X交换
4，重复步骤2，3，直到i=j；
这样一趟快速排序就完成了；第一趟完成之后，X左边的数就全部小于X了，X右边的数九全部大于X，然后采用递归方式对X左边的数和X右边的数进行快速排序。
            /**  
     * @param pData 需要排序的数组  
     * @param left  左边的位置,初始值为0  
     * @param right 右边的位置,初始值为数组长度  
     */   
    public static void QuickSort(int[] pData,int left,int right)   
    {   
          int i,j;   
          int first,temp;   
          i = left;   
          j = right;   
          first = pData[left]; //这里选其他的数也行，不过一般选第一个  
          //一趟快速排序   
          while(true)   
          {   
              //从第二个数开始找大于中枢的数 ,从前面开始找大于pData[left]的数  
              while((++i)<right-1 && pData[i]<first);   
              //从最后一个数开始找第一个小于中枢pData[left]的数   
              while((--j)>left && pData[j]>first);   
              if(i>=j)   
                  break;   
              //交换两边找到的数   
              temp = pData[i];   
              pData[i] = pData[j];   
              pData[j] = temp;   
          }   
          //交换中枢   
          pData[left] = pData[j];   
          pData[j] = first;   
          //递归快排中枢左边的数据   
          if(left<j)   
            QuickSort(pData,left,j);   
          //递归快排中枢右边的数据   
          if(right>i)   
            QuickSort(pData,i,right);   
    }    


















来自为知笔记(Wiz)


判断一个数是否是素数


联系
我们