betway必威-betway必威官方网站
做最好的网站

betway必威官方网站:Java卓绝算法,素数表的得到

程序分析: 贰个过量1的正整数,假使除去一和它自个儿以外,不可能被别的正整数整除,就叫素数。

一:有1对兔子,从出生后第13个月起种种月都生1对兔子,小兔子长到第五个月后种种月又生一对兔子,若是兔子都不死,问每一种月的兔子总的数量为多少?
  • 深入分析:兔子对数的规律为数列一,壹,二,三,五,8,壹3,2一....,即每过八个月兔子的挑衅者是前三个月之和,运用递归的合计即math(x-1) math(x-2)。好程序如下:
public class Test01 {
    public static void main(String[] args) {
        int i = 0;
        for(i=1;i<=20;i  ){
            System.out.println("第" i "月的兔子个数为:" math(i)*2);
        }
    }

    private static int math(int i) {
        if(i==1||i==2){
            return 1;
        }
        return math(i-1) math(i-2);
    }
}

素数与素数表基本概念##

素数又称之为质数,是指除了一和自身之外,无法被其余数整除的一类数。注意: 一既不是素数,也不是合数。

直白对于自然范围内的素数举行判定求取素数表,采取直接省略遍历的主意,那样的时光复杂度为O(n),那么只要采用加速的章程能够那样深入分析:
如果在2 ~ n-第11中学存在n的约数,那么无妨设那么些约数为k,那么由k*(n/k) ==n可见,n/k也是n的三个约数,并且k与n/k必然一个稍低于sqrt(n),而另3个超越sqrt(n),通过那样的笔触就足以减低算法的复杂度。

亲自过问代码:

bool isPrime(int n) {
    if(n <= 1) return false; // 特判
    int sqr = (int)sqrt(1.0 * n);  //求得根号n
    for(int i = 2; i < sqr; i  ) {  // 遍历2~根号n
        if(n % i == 0) return false; // n是i的倍数,则n不是素数
    }
    return true; // n是素数
}

上述代码照片非常,sort的功用是为三个浮点数开根号,必要加多math.h头文件。

鉴于sqrt的参数须要是浮点数,因而在n前边供给乘上一.0使其改为浮点型。

1、参考解法: 决断素数的方法:用3个数分别去除二到sqrt(这么些数),要是能被整除,则表明此数不是素数,反之是素数。

二:推断十一-200之内有多少个素数,并出口全数素数。
  • 浅析:假设该数能被贰整除即不是素数反之便是素数,代码如下:
public class Test02 {
    public static void main(String[] args) {
        int count = 0;
        int j = 2;
        for (int i = 101; i < 201; i  ) {
            for(j=2;j<i;j  ) {
                if ((i % j) == 0) {
                    break;
                }
            }
            if (j==i) {
                count  ;
                System.out.println(i "这个数为素数");
            }
        }
        System.out.println("101-200之间一共" count "个素数");
    }
}

素数表的收获##

用以上的秘技完毕素数表的获得,时间复杂度为O(n*根号n)
1经现身大范围素数表需要求解,以上解法将不可能,所以能够选用各个“筛法”,个中“埃式筛法”是最简易的壹种。那样的复杂度能够下跌到O(nloglogn)。

事实上“埃式筛法”正是只要本身开采了某3个数是1个素数,那么这些数的富有倍数,都不是素数了,就把那个倍数全体筛掉了。所以这里就须求保障八个数组,1个道理当然是那样的用来存放素数,此外1个正是存放标记位,这些数组的下标代表的便是数字,标识位就代表那些数值是或不是现已检查过了。

这里拿2个例题讲明:

求正整数M~N之间的具有素数:

算法代码:

#include <stdio.h>
const int maxn = 1000001;
int prime[maxn], num = 0;
bool p[maxn] = {0};
void Find_Prime (int n) {
    for(int i = 2; i < maxn; i  ) {
        if(p[i] == false) {
            prime[num  ] = i;
            // 只需要n个素数,因此超时即可结束
            if(num >= n) break;
            for(int j = i   i; j < maxn; j  =i) {
                p[j] = true;// 都不是素数
            }
        }
    }
}

int main() {
    int m, n, count = 0;
    scanf("%d%d", &m, &n);
    Find_Prime(n);
    // 输出从第m个素数至第n个素数
    for(int i = m; i <= n; i  ) {
        // 下标从0开始
        printf("%d",prime[i - 1]);
        count  ;
        if(count % 10 != 0 && i < n) printf(" ");
        else printf("n");
    }
    return 0;
}

此间供给小心的几点:

  • 一不是素数
  • 素数表长至少要比n大一
  • 在Find_Prime()函数中要特地专注 i < maxn 不能够写成 i <= maxn
  • main函数中要记得调用Find_Prime(),不然不会油不过生结果
from math import sqrt
h=0
for m in range(101,201):
    leap=1
    k = int(sqrt(m))        #返回数字的平方根
    for i in range(2,k 1):#K 1,表示从2循环到K(包含k)
        if m % i==0:
            leap=0
            break
    if leap==1:
        print('%-4d'%m)
        h =1
        if h % 10==0:
            print('')
print('The total is %d'%h)
三:打字与印刷出富有的 "雅蒜数 ",所谓 "金盏银台数 "是指一个四个人数,其各位数字立方和相当该数本人。 比方:一伍叁是多少个 "水仙花数,因为壹5叁=一的一次方+5的一遍方+三的壹回方。
  • 剖判:将各位数抽出后实行Math.pow(x,3)并求和要是等于原始数即为姚女子花剑数,代码如下:
public class Test3 {
    public static void main(String[] args) {
        for (int i = 100; i <= 999; i  ) {
            if (i == math(i)) {
                System.out.println(i   "是一个水仙花数");
            }
        }
    }

    private static int math(int i) {
        int g = i;
        int s = i0/10;
        int b = i/100;
        return (int) (Math.pow(b,3) Math.pow(s,3) Math.pow(g, 3));
    }
}

   

四:将2个正整数分解质因数。举个例子:输入90,打字与印刷出90=二33*5。
  • 浅析:借使该数能被二个稍低于它的数整除,那么利用递归将商传递下去,直到获得2个只能被该数本人整除的数截至递归。代码如下:
public class Test04 {
    StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个正整数:");
        String n = scan.next();
        System.out.print(n "=");
        math(Integer.valueOf(n));
    }

    private static void math(int n) {
        for(int i=2;i<n;i  ){
            if (n%i==0) {
                System.out.print(i "*");
                math(n/i);
            }
        }
        System.out.println(n "");
        System.exit(0);// 不能少了这一句
    }
}

二、参照他事他说加以考察解法:

5:利用规范运算符的嵌套来成功此题:学习成绩> =捌拾柒分的同窗用A表示,60-87分之间的用B表示,陆拾叁分以下的用C表示。
  • 剖析:条件运算符的格式判断条件?条件成立的结果:条件不成立的结果。代码如下:
public class Test05 {
    public static void main(String[] args) {
        Random random = new Random();
        int n = random.nextInt(101);
        String str = (n<60?"C":(n<90?"B":"A"));
        System.out.println("该学生的成绩是:" n ",评级为:" str);
    }
}

运用函数解法

6:输入四个正整数m和n,求其最大公约数和最小公倍数。
  • 解析:辗转相除法,又称欧几里得算法。几个整数的最大公约数是力所能致同时整除它们的最大的正整数。辗转相除法基于如下原理:多个整数的最大公约数等于在那之中比较小的数和两数的差的最大公约数。这里刚开始的时候使用一种相比笨的办法来求最小公倍数,作为1种思路也发放大家看看啊。代码如下:
public class Test06 {
    public static void main(String[] args) {
        Random random = new Random();
        int a = random.nextInt(300);
        int b = random.nextInt(300);
        int gcd = countGCD(a,b);// 求最大公约数的方法
        //int lcm = countLCM(11,10);// 求最大公倍数的方法
        int lcm = a*b/gcd;// 两个数的乘积等于最大公约数与最小公倍数的乘积
        System.out.println(a "," b " 的最大公约数为:" gcd);
        System.out.println(a "," b " 的最小公倍数为:" lcm);
    }

    private static int countLCM(int a, int b) {
        int t = a>b?a:b;
        while(true){
            if(t%a==0&&t%b==0){
                return t;
            }
            t  ;
        }
    }

    private static int countGCD(int a, int b) {
        while(true){
            if((a=a%b)==0){
                return b;
            }
            if((b=b%a)==0){
                return a;
            }
        }
    }
}

本文由betway必威发布于编程开发,转载请注明出处:betway必威官方网站:Java卓绝算法,素数表的得到

TAG标签: betway必威
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。