ruby判定叁个数是或不是为质数

1、依据质数的定义求

质数又称素数。三个超乎1的自然数,假如除去1和它本人外,不可能被其余自然数整除的数;(除0以外)否则称为合数
。依照算术基本定理,每二个比1大的莫西干发型,要么自个儿是一个质数,要么可以写成一连串质数的乘积;况且一旦不思虑这一个质数在乘积中的顺序,那么写出来的样式是头一无二的。

1、依据质数的定义求
  质数定义:只好被1大概本人整除的自然数(不包含1),称为质数。
  利用它的概念能够循环决断该数除以比它小的种种自然数(大于1),借使有能被它整除的,则它就不是质数。
对应代码是:

  质数定义:只好被1如故作者整除的自然数(不满含1),称为质数。
  利用它的概念能够循环决断该数除以比它小的种种自然数(大于1),假如有能被它整除的,则它就不是质数。
对应代码是:
void printPrime(int n){//推断n是或不是是质数
        boolean isPrime=true;//是还是不是是质数的标记
        for(int i=n-1;i>1;i—){//n除以每一种比n小比1大的自然数
            if(n%i==0){//即使有能被整除的,则不是质数
                isPrime=false;
            }
        }
        if(isPrime){//假设是质数,则打字与印刷出来
            System.out.print(n+” “);
            primeNumber++;//记录质数的个数
            if(primeNumber%10==0)//输出12个质数后换行
                System.out.println();
        }
}
2、利用叁个定律——要是一个数是合数,那么它的最小质因数一定小于等于他的平方根。举个例子:50,最小质因数是2,2<50的开根号
再例如:15,最小质因数是3,3<15的开根号
  合数是与质数相呼应的自然数。三个胜出1的自然数如若它不是合数,则它是质数。
  上边的定律是说,若是多个数能被它的最小质因数整除的话,那它料定是合数,即不是质数。所以判别三个数是还是不是是质数,只需判别它是或不是能被小于它开跟后后的全部数整除,那样做的演算就能够少了过多,因而作用也高了非常多。
对应代码是:
void printPrime(int n){//判定n是不是是质数
求质数的三种算法,ruby判定贰个数是或不是为质数。        boolean isPrime=true;//是还是不是是质数的注明
        int s=(int)Math.sqrt(n);//对n开根号
        for(int i=s;i>1;i—){//n除以每种比n开根号小比1大的自然数
            if(n%i==0){//假使有能被整除的,则不是质数
                isPrime=false;
            }
        }
        if(isPrime){//倘若是质数,则打字与印刷出来
            System.out.print(n+” “);
            primeNumber++;//记录质数的个数
            if(primeNumber%10==0)//输出十个质数后换行
                System.out.println();
        }
}
3、筛法求质数,效用最高,但会比较浪费内部存款和储蓄器
  首先创设一个boolean类型的数组,用来存款和储蓄你要咬定有个别范围内自然数中的质数,举个例子,你要出口小于200的质数,你供给树立三个大大小小为201(创立201个存款和储蓄地点是为着让数组地点与其尺寸同等)的boolean数组,开始化为true。
  其次用第两种艺术求的率先个质数(在此是2),然后将是2的倍数的数全置为false(2除此之外),即2、4、6、8……地方上置为false。然后是
3的翻番的全置为false(3除了),一直到14(14是200的开平方),那样的话把不是质数的职责上置为false了,剩下的全都是质数了,挑着是
true的打字与印刷出来就行了。
对应代码是:
boolean[] printPrime(int range){
        boolean[] isPrime=new boolean[range+1];
        isPrime[1]=false;//1不是质数
        Arrays.fill(isPrime,
2,range+1,true);//全置为true(大于等于2的地点上)
        int n=(int)Math.sqrt(range);//对range开根号
        for(int i=2;i<=n;i++)//注意供给小于等于n
            if(isPrime[i])//查看是还是不是曾经置false过了
                for(int
j=i;j*i<range;j++)//将是i倍数的地点置为false
                    isPrime[j*i]=false;
金沙注册送58 ,        return isPrime;//重回三个boolean数组
}

复制代码 代码如下:

        /// <summary>
        /// 输出从2到max的所有质数
        /// </summary>
        /// <param name="max"></param>
        public static void Prime(int max)
        {
            bool flag = false;
            int count = 0;
            for (int i = 2; i <= max; i++)
            {
                flag = IsPrime(i);
                if (flag)
                {
                    Console.Write("{0,3} ",i);
                    count++;
                    if (count % 8 == 0)
                    {
                        Console.WriteLine();
                    }
                }

            }
        }

        /// <summary>
        /// 判断输入的数字是否是质数
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static bool IsPrime(int n)
        {
            bool flag = true;
            if (n < 2)
            {
                throw new ArgumentOutOfRangeException();
            }
            for (int i = 2; i <= n - 1; i++)
            {
                if (n % i == 0)
                {
                    flag = false;
                    break;
                }
            }
            return flag;
        }

def prime?(num)
  res = [1]
  res << num

金沙注册送58 1
2、利用一个定律——假如二个数是合数,那么它的最小质因数一定小于等于他的平方根。比如:50,最小质因数是2,2<50的开根号
再举个例子说:15,最小质因数是3,3<15的开根号
  合数是与质数相对应的自然数。二个超乎1的自然数借使它不是合数,则它是质数。
  上面的定律是说,假使三个数能被它的最小质因数整除的话,那它断定是合数,即不是质数。所以推断四个数是不是是质数,只需剖断它是或不是能被小于它开跟后后的全体数整除,那样做的运算就能够少了累累,由此功用也高了重重。
对应代码是:

  if num == 0 || num == 1
    return false
  end

只供给将从前的质数判别更动一下就可以了

  2.upto(10) do |x|
    #假定有友好的话,就跳下一次巡回
    if num == x
      next
    end

        /// <summary>
        /// 判断输入的数字是否是质数
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static bool IsPrime(int n)
        {
            bool flag = true;
            if (n < 2)
            {
                throw new ArgumentOutOfRangeException();
            }
            int max = Convert.ToInt32(Math.Floor(Math.Sqrt(n)));
            for (int i = 2; i <= max; i++)
            {
                if (n % i == 0)
                {
                    flag = false;
                    break;
                }
            }
            return flag;
        }

    #拜望是或不是能被 2-10时期的数整除, 取余数约等于分组
    if num % x == 0
      res << x
    end
  end

 

  res.length > 2 ? false : true
end

3、筛法求质数,功用最高,但会相比浪费内部存款和储蓄器
  首先创建叁个boolean类型的数组,用来囤积你要决断有个别范围内自然数中的质数,举例,你要出口小于200的质数,你须求树立贰个轻重为201(创建201个存款和储蓄地方是为着让数组地点与其大小同等)的boolean数组,初叶化为true。
  其次用第三种办法求的率先个质数(在此是2),然后将是2的倍数的数全置为false(2除却),即2、4、6、8……地点上置为false。然后是3的倍数的全置为false(3除了),一贯到14(14是200的开平方),那样的话把不是质数的岗位上置为false了,剩下的全部是质数了,挑着是true的打字与印刷出来就行了。
对应代码是:

 /// <summary>
        /// 输出从2到n的所有质数
        /// </summary>
        /// <param name="n"></param>
        public static void Prime(int n)
        {
            bool[] array = new bool[n + 1].Select(x => x = true).ToArray();
            array[1] = false;
            int count = 0;
            int sqrt = Convert.ToInt32(Math.Floor(Math.Sqrt(n)));
            for (int i = 2; i <= sqrt; i++)
            {
                for (int j = i; j * i <= n; j++)
                {
                    array[j * i] = false;
                }
            }
            for (int i = 1; i <= n; i++)
            {
                if (array[i])
                {
                    Console.Write("{0,3} ", i);
                    count++;
                    if (count % 8 == 0)
                    {
                        Console.WriteLine();
                    }
                }
            }
        }

 

相关文章

网站地图xml地图