saber酱的抱枕

Fly me to the moon

08/27
02:49
学习

JavaScript 判断数字是否是质数

JavaScript 判断数字是否是质数

看到了一个 JavaScript 面试题,编写一个函数 isPrime,检查输入的参数是否是质数。

质数又称素数,定义为在大于1的自然数中,除了 1 和它本身以外不再有其他因数。也就是只能被 1 和它自身整除。

质数列表如: 2 3 5 7 11 13 17 19 23 ……

要点:
1.质数只能是正整数,所以负数、0、小数都不是质数。
2.质数是从 2 开始的,2 比较特殊,是质数里唯一一个偶数。对 2 要单独处理。
3.大于 2 的偶数都不是质数,因为可以被 2 整除。所以我们可以直接排除偶数,提高效率。
4.把奇数开平方,让奇数依次除以 3、5、7……一直到它的平方根,看有没有能整除的,如果有那就不是质数。

开平方这一步可以大大提高效率,它的数学原理我也不是很懂,据我猜测大概如下:

599/3=199.66666666666666
599/199=3.0100502512562812

用 599 除以 3,或者除以 199,其实就相当于把 除数 和 商 颠倒了一下,所以没必要两个都验证,只验证 3 就可以了。

数字 599 的平方根约为 24,我们验证到 24 就可以停了,因为验证 24 之后的数字,其实就类似上面的情况,没有必要。


如果不考虑对输入的数据做判断,就很简单,大概这样:

function isPrime(num) {
	// 排除不在质数范围内的数字(处理负数、0、1)
	if (num < 2) {
		return false;
	}
	// 2 是特例,单独处理(处理2)
	if (num === 2) {
		return true;
	}
	// 如果是偶数,则直接输出结果(处理大于2的偶数)。这样可以提高效率
	if (num % 2 === 0) {
		return false;
	}
	// 处理大于2的奇数
	let sq = Math.sqrt(num); // 开平方,验证时数字不大于平方
	// 从除以 3 开始验证,只验证奇数,到平方根停止。
	for (let index = 3; index <= sq; index += 2) {
		if (num % index === 0) { // 未通过检查
			return false;
		}
	}
	// 检查通过
	return true;
}

但是数据验证还是必要的,我自己琢磨了琢磨。

比如输入值为 true、 null 这种,可以强制转换成数字 0,但这根本和数字没半毛钱关系,所以判断时不要用强制转换。
比如要排除带小数点的数字,但我发现对于很大的数字,JavaScript 无法判断它有没有小数点。
对于很大的数字,就算不考虑小数点,JavaScript 也根本无法正确的计算。

这些关于数字的验证坑了我不少时间。最后看参考答案,丫根本不做验证的,坑爹啊

// 质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。
// 不要使用超出 JavaScript 精确整数范围的数字(−9007199254740992 至 9007199254740992,即正负2的53次方),否则无法正确处理。
// 检查数字是否是质数。参数只允许数字和字符串形式的数字
function isPrime(num) {
	// 排除不希望接收的的参数 * 0
	if (isNaN(parseInt(num))) {
		console.error('不是数字');
		return false;
	}
	// 转换成数字 * 1
	num = Number(num);
	// 判断数字范围
	if (num < -9007199254740992 || num > 9007199254740992) {
		console.log('%c超出处理范围', 'color:#EB3941;');
		return false;
	}
	// 排除带小数的 * 2
	if (num.toString().indexOf('.') > -1) {
		console.log('%c有小数点', 'color:#EB3941;');
		outputResult(false);
		return false;
	}
	// 排除不在质数范围内的数字(处理负数、0、1)
	if (num < 2) {
		outputResult(false);
		return false;
	}
	// 2 是特例,单独处理(处理2)
	if (num === 2) {
		outputResult(true);
		return true;
	}
	// 如果是偶数,则直接输出结果(处理大于2的偶数)。这样可以提高效率
	if (num % 2 === 0) {
		outputResult(false, 2);
		return false;
	}
	// 处理大于2的奇数
	let sq = Math.sqrt(num); // 开平方,验证时数字不大于平方
	// 从除以 3 开始验证,只验证奇数,到平方根停止。
	for (let index = 3; index <= sq; index += 2) {
		if (num % index === 0) { // 未通过检查
			outputResult(false, index);
			return false;
		}
	}
	// 检查通过
	outputResult(true);
	return true;

	// 输出结果的函数
	function outputResult(bool, find) {
		if (bool) {
			console.log('%c是质数', 'color:green;');
		} else {
			if (find) {
				console.log(`%c可以被 ${find} 整除`, 'color:#666;');
			}
			console.log('%c不是质数', 'color:#EB3941;');
		}
	}
}

// 测试
isPrime(5415646465464617);

/**
 	* 0:
	判断参数时为什么使用 parseInt 而不是 Number,因为它们的转换结果有区别 :
	比如我们不想接受 true、false、null、[]、'' 等非数字内容:
	使用 parseInt() 它们会被转换成 NaN,这样可以排除这些参数。
	如果使用 Number(),它们会被强制转换成数字 0 或 1,不能起到排除效果。

	* 1:
 	参数通过检查后,转换成数字开始使用时,使用 Number()比较好。因为 parseInt() 处理的上限不够大,Number() 的范围更大:
	parseInt(5415646465464654456465646546545646) // 5 这个结果是错误的
	Number(5415646465464654456465646546545646)	// 5.415646465464654e+33 这个错的没那么严重,其实也不对
	它相当于只能表示到 5415646465464654 ,后面那部分数字被舍弃了。因为这个完整的数字超出了 9007199254740992 。

	对于超出 JavaScript 精确整数范围的数字,使用 Number() 比 parseInt() 好一点,错的没那么严重。但其实都不准确了,这里只是提一下。

	* 2:
	这个方法判断小数时,把数字转换成字符串,查找带不带小数点。但是对于科学计数法的数字,以及超出处理范围的数字来说,都无法准确判断。
	如 5415646465464654456465646546545646 没有小数,但转换成字符串是科学计数法的 "5.415646465464654e+33",这样就有了点 . ,会被判断成小数。
	有时候,即使数字本身带小数,但超出处理范围,就无法分辨了。如 JavaScript 认为 5415646465464654456465646546545646.5 和它不带小数时是一样的(全等)。
	这种超大数字也许用其他编程语言处理更合适。如这个查素数的网站,就是把数字传到服务器上计算的,而不是用 JavaScript 直接计算。
	http://www.haomeili.net/ZhiShu/IsZhiShu
 */

JavaScript 判断数字是否是质数

  1. akari
    Google Chrome 57Google Chrome 57Android 8.0.0Android 8.0.0

    如果算大于平方根的数的话就差不多是重复前面(平方根)的过程了~
    反证一波~假设某数x可由两个素数相乘所得,则x不为素数;若这两个素数相等,就是平方根的情况;若不等,由乘法交换律,小乘大等于大乘小,一样的。如果在比平方根小的半区检验不出,那如果在大的半区检验到了符合条件的素数(奇数)b,那对应的奇数a就在小半区,与前设条件矛盾。所以。。。
    ╮(╯_╰)╭
    脑袋抽风,这条评论画风不对

    回复
      1. znbc
        Firefox 56Firefox 56WindowsWindows

        费马小定理
        若p为质数,则对于所有于p互质的a,a的p-1次方模p为1(模就是求余数,运算符号是%)
        a,p互质其实就是a不是p的倍数,因为p是质数
        所以如果存在a使得a的p-1次方模p不为1,则p不是质数(逆否命题)
        但是这个结论反过来不一定成立(反命题),就是说对于某些合数,也能找到对应的a,使a的p-1次方模p为1。
        但是这种情况比较少见。所以如果对一个数x,有一个a满足a的x-1次方模x为1,那么可以说这个数很可能是质数,或者说这个数是质数的概率是s,不是质数的概率1-s。
        所以如果对于多个不同的a1,a2,...an,均满足上面条件,那么这个数不是质数的概率就是
        (1-p1)*(1-p2)*...(1-pn)趋于零,只要这些a取得足够多并且足够好,那么满足ai的x-1次方模x为1的x就可以可以认为是质数。
        一般的质数判别法(验证1到根号x是不是整除x)可以很容易的判断int类型范围以内的质数,但是对于200位左右的数字无能为力(运算到宇宙毁灭),但是这种方法却很快,虽然并不是完全正确,但是够用了。
        另外如果要产生1到x之内所以的质数,可以用筛法。
        本来是看小黄油的结果居然在讨论数学。。。
        不过这个问题还是很基础的,博主加油

        回复

评论 akari 撤销评论