【陆丁导读】本文主要阐述了素数的概念,用通俗易懂的方式形象地描述了素数和合数的含义,找到了在给定数值范围内求素数的方法。
二。文章大纲
1、素数的概念
2、对质数形象的理解
3.什么是合数?
4、为什么1不是质数
5.如何求给定范围内的质数
6、Python中求素数的例子
也叫质数,它的英文名是Prime number。
三。文章内容
1,素数的概念至于质数,也叫质数。从字面上可以想象,这个数有一个基本的、本质的、原子的意义。也就是说,这个数不能再分裂,是一个基本的、独立的原子个体。质数的定义是指不能被除1以外的其他自然数和整数本身(1除外)整除的数。
2,素数的形象的理解你可以想象,有一堆苹果,n个,假设苹果没有切开,现在你需要把这堆苹果平均分给几个人。
有两种可能的结果,一种是可以分成几等份;一个是一堆不能再分的苹果,保持原样。
对于第二种情况(保持原样,不能再分了),这堆苹果可以看做以下两种情况:
a、以单个苹果为个体,可分为N人,1(一)*n(人)
b、取n个苹果为一个整体,可以分给一个人,n(苹果)*1(人);
回到数的范畴,即如果一个整数n只能被1或自身整除,也就是说,这个整数n只能用n=1*n或n=n*1的形式来表示,也就是说,它不能被分成其他形式的等份,那么这个数就叫做素数。
形象的理解为:一堆苹果,还是原来的那堆苹果,没变。
3,什么是合数遵循上面素数的概念,相反,如果一堆苹果可以细分成n=a*b (a,b不等于1或n)的形式,那么n称为合数。“组合数”这个词本身也意味着几个数可以组合在一起。
以苹果为例。假设这堆苹果中有15个。除了15的状态,还可以分为三堆、五堆(3*5)或五堆(5*3)。也就是说,15不仅可以表示为15*1或1*15,还可以表示为3*5或5*3。换句话说,15可以被3或5整除,除了被1和它本身整除。
4,为什么1不是素数其实从本质的概念来说,1也可以称为素数,从上面的例子就可以看出来。
现在不能把1当作素数的原因是,如果把1当作素数,合数的概念就不一致了。
合数,从上面第3点的分析我们可以知道,合数n可以用n=a*b的形式表示(其中a和b不等于1或n)。
既然n=a*b,那么a和b有两种状态,要么是质数,要么是合数。为什么?
因为,数本身只有这两种状态:要么只能被1或自身整除,要么可以被其他数除除除。因此,数字A和B可能是质数,也可能是合数。
现在,我想对A和B做如下处理:如果是质数,保持不变;如果是合数,那么继续分解成两个数的乘积。
就这样,它一直运行下去,n=a*b,最后会以n=p1*p2*p3的形式呈现出来...(其中p1、p2、p3...都是质数)。也就是说,一个合数最终会被表示为质数的乘积。
现在回到本题的问题,为什么1不是质数?
因为:1由于其特殊性(1乘以1或1的任意数),一个合数n=p1*p2*p3会有无数个表达式。也就是说,合数n可以表示为:
n=p1*p2*p3
n=p1*p2*p3*1
n=p1*p2*p3*1*1
n=p1*p2*p3*1*1*1
......
因此,为了实现合数表达式的唯一性,1被人为地排除在素数之外。
5,如何求给定范围内的素数到目前为止,质数和合数都是已知的。所以如果你想问在给定的数的范围内有哪些素数,应该怎么找?
比如如何求10以内的质数?
根据常识,我们很容易想到10以内的质数:2,3,5,7。
如果不是10,而是100以内的质数呢?
是依次数,2,3,5,7,11,13,17,19吗?...
如果不是100,而是1000以内的质数呢?
好像凭自己的理解去算,会让人昏了头,这不是解决问题的根本办法。
那么应该怎么解决呢?
在我看来,还是要从质数的概念说起:只能被1和自己整除的数。
即除了1和它本身不能被其他数整除的数。或者说,只要找到一个能被1和它本身整除的数,就可以确定这个数不是素数。
下面的目标是试图找到这样的数字。
先想想不是质数的数。它是什么号码?答案很明显,就是和数。合数的性质是什么?合数可以表示为几个质数的乘积。
既然要求是n以内的质数,那么n以内的质数一定是n以内的;n以内的合数也在n以内,n以内的合数可以表示为几个素数的乘积,这里的素数必须在n以内。
那么就可以确定n以内的一个合数会被n以内的至少一个素数整除,如果我们能找到这样一个能被n以内的一个合数整除的最大素数K,那么我们就能得到这样一组素数(从2开始,最大值为K)。我们将依次对n以内的整数和这个集合中的素数进行补数运算,根据补数结果是否为0来判断整数是否为合数。也就是说,余数的结果要么是0的整数,要么是素数。
下面的问题是:给定整数范围N,如何求能被N内的合数整除的最大素数?
从合数的概念来看,一个合数可以表示为几个素数的乘积。
至于一个合数分解成的素数的个数,这个是不确定的。可能是两个,三个或者更多。
这里有一个结论:
假设一个合数M可以分解成三个素数的乘积,M = x1 * x2 * x3(x1 < = X2 lt;=X3),然后开m的平方根3次,得到的结果是一个整数I,I必须在m的素数中间,即I >;=X1和I
那么,现在我们知道了,如何在给定的整数范围内找到一个素数:
根据上面讨论的方法,现在用Python实现了一个程序来寻找给定整数范围内的素数。
Python实现代码(在给定的整数范围内寻找素数)
验证结果: