mysql寻找质数的方法

发表于 2017-12-20 分类于 MySQL 阅读次数：阅读次数：本文字数： 590 阅读时长 ≈ 2 分钟

问题：用sql求出1000以内的质数？输出形式为：

2&3&5&7

求质数算法其实不算难，运用循环的方式对大部分的程序语言来讲都不男写，但sql是个例外。循环对于普通的sql并不好写，除非采用存储过程。

数学定义

数学中的定义是这样的：素数，又称为质数，是指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数。或者说素数是只有1和本身两个因数的数。

一般解法

验证素数的算法可分为两大类，即确定性算法及随机算法。确定性算法中最常用的就是试除法。试除法是根据素数的定义得出的一种方法，用需要验证的数N逐个除以从2开始至N－1中的所有数，若能被某一个数整除，表示有一个因数，说明数N不是素数；若直到N－1都不能被整除，则说明该数是素数。

从上面的思路可以得出的一般算法就是双重迭代的方式。

boolean isPrime(int n){
  if(n<=1){
    return false;
  }
  for(int i=2;i<n;i++){
    if(n%i ==0){
      return false;
    }
  }
  return true;
}

升级解法

其实，可以对素数的定义进行进一步的分析。要判断数N是否为素数，不需要用N一直除到N－1才能确认，而只需要除到就可以了。
解法就是整数做被除数，所有比他小的数做

boolean isPrime(int n){
  if(n<=1){
    return false;
  }
  for(int i=2;i*i<=n;i++){
    if(n%i ==0){
      return false;
    }
  }
  return true;
}

sql解法

sql用sql实现上述过程，就比较困难了。需要借助一些特殊的方式。

SELECT
	GROUP_CONCAT(NUMB SEPARATOR '&')
FROM
	(
		SELECT
			@num :=@num + 1 AS NUMB
		FROM
			information_schema. TABLES t1,
			information_schema. TABLES t2,
			(SELECT @num := 1) tmp
	) tempNum
WHERE
	NUMB <= 1000
AND NOT EXISTS (
	SELECT
		*
	FROM
		(
			SELECT
				@nu :=@nu + 1 AS NUMA
			FROM
				information_schema. TABLES t1,
				information_schema. TABLES t2,
				(SELECT @nu := 1) tmp1
			LIMIT 1000
		) tatata
	WHERE
		FLOOR(NUMB / NUMA) = (NUMB / NUMA)
	AND NUMA *NUMA <= NUMB
	AND NUMA > 1
)