精华内容
下载资源
问答
  • 用c语言,找出指定范围内的质数

    千次阅读 2016-11-25 23:53:30
    最近在学C语言,在MOOC上看到翁恺老师讲的《程序设计入门——C语言》,学到老师讲到怎么用C语言测试一个数是否为整数的时候,突然想到,既然可以测试怎么一个数是否为整数,那么肯定能够找出一定范围内的数是否为...

    最近在学C语言,在MOOC上看到翁恺老师讲的《程序设计入门——C语言》,学到老师讲到怎么用C语言测试一个数是否为整数的时候,突然想到,既然可以测试怎么一个数是否为整数,那么肯定能够找出一定范围内的数是否为整数了。

    于是想了想,用了如下代码,可以简单的实现这个功能,代码如下:

    #include <stdio.h>
    
    int main(){
    	int number;
    	int i,j,flag=1;
    
    	scanf("%d",&number);
    	for(i=2; i<number; i++){
    		for(j=2; j<i; j++){
    			if(i%j==0){
    				flag=0;
    				break;
    			}
    		}
    		if(flag!=0&&j==i){
    			printf("%d ",i);
    		}
    		flag=1;
    	}
    	printf("\n");
    	return 0;
    }


    展开全文
  • 质数的定义:指在大于1的自然数中,除了1和它本身以外不再有其他...分为偶数和奇数,合数和质数等(百度百科)问题:怎么找出n(n为大于2的自然数)内的全部质数?我们已知大于2的偶数自然数均为合数,大于2的奇数自然数...

    质数的定义:指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数(百度百科)

    自然数的定义:指用以计量事物的件数或表示事物次序的数。即用数码0,1,2,3,4……所表示的数。自然数由0开始,一个接一个,组成一个无穷的集体。自然数有有序性,无限性。分为偶数和奇数,合数和质数等(百度百科)

    问题:怎么找出n(n为大于2的自然数)内的全部质数?

    我们已知大于2的偶数自然数均为合数,大于2的奇数自然数却由质数和合数组成。那么,如果我们把奇数中的合数全部去掉(合数有质数相乘得到的,如:10=2*5),奇数中的剩余部分便全是质数了,最后添加一个2便是最终结果。举例说明:

    现求100以内的全部质数,将[3,100]区间的数据分为奇数和偶数,偶数部分全为合数,奇数部分有3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99。(以下的数字都是此数据中的数)

    第一个数字是3(质数),我们先除去range(3*2,101,2*3)的合数(因为奇数*偶数=偶数,奇数+偶数=奇数,偶数已被我们剔除,所以乘奇数倍),得到的结果有3,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97

    第二个数字是5(质数),再除去range(5**2,101,2*5)。得到的结果有3,5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97

    第三个数字是7(质数),再出去range(7**2,101,2*7),得到的结果有3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

    第四个数字是9(合数),过

    第五个数字是11(质数),但是11**2>100,则第五个数字后都不用管,再第三步的结果中添加2变为100内的全部质数。

    而大于2的全部合数是:range(4,101,2),range(9,101,6),range(25,101,10),range(49,101,14)

    以下是python提取质数的代码过程(返回的集合,i5处理器,10000000内的全部质数耗时约2.3s):

    from itertools import chain

    def prime_set3(a):

    b=[] # 存放合数

    for i in range(3, int(a**0.5)+1, 2):

    number = 0

    for n in range(3, i, 2):

    if i % n == 0 and i > n:

    number = 1

    break

    if number == 1:

    continue

    b.append(range(i**2, a+1, 2*i))

    aa = set(chain([2],range(3, a+1, 2)))

    bb = set(chain(*b))

    prime = aa - bb

    return prime

    以下是上述代码的雏形:

    from itertools import chain

    def prime_set(a):

    b=[]

    for i in range(2,int(a**0.5)+1):

    b.append((range(i**2,a+1,i)))

    sa=set(range(2,a+1))

    sb=set(chain(*b))

    prime=sa-sb

    return prime

    展开全文
  • 之前在某次interview中被老外问到如何用SQL找出列上的质数和完全数的问题;我当时已经多年没有写过这种考算法和SQL技巧(纯粹的技巧)的语句了,乍遇此问题倒是有些棘手。现在录以记之,供人参考.SQL> create table...

    之前在某次interview中被老外问到如何用SQL找出列上的质数和完全数的问题;我当时已经多年没有写过这种考算法和SQL技巧(纯粹的技巧)的语句了,乍遇此问题倒是有些棘手。现在录以记之,供人参考.

    SQL> create table numbers(NO int) ;

    表已创建。

    SQL> insert into numbers  select rownum  from dba_objects;

    已创建71937行。

    SQL> commit;

    提交完成。

    SELECT X.NO as Primes  /*查找质数(find prime number)*/

    FROM Numbers N

    CROSS JOIN Numbers X

    WHERE mod(X.NO, N.NO) != 0

    AND N.NO < X.NO

    GROUP BY X.NO

    HAVING(X.NO - Count(*)) = 2;

    PRIMES

    ---------

    4931

    4919

    4909

    4903

    4889

    4877

    4871

    4861

    4831

    4817

    4813 ................

    SELECT X.no as Perfect /*查找完全数,find perfect nober*/

    FROM numbers N

    CROSS JOIN numbers X

    WHERE mod(X.no, N.no) = 0

    and X.no > 1

    AND N.no < X.no

    AND N.no > 0

    GROUP BY X.no

    HAVING SUM(N.no) = X.no;

    PERFECT

    ----------

    6

    28

    496

    ......................

    附:

    select ltrim(sys_connect_by_path(rownum || '*' || lv || '=' ||  /* SQL_99乘法口诀表*/

    rpad(rownum * lv, 2),

    '  '))

    from (select level lv from dual connect by level < 10)

    where lv = 1

    connect by lv + 1 = prior lv;

    1*1=1

    2*2=4   2*1=2

    3*3=9   3*2=6   3*1=3

    4*4=16  4*3=12  4*2=8   4*1=4

    5*5=25  5*4=20  5*3=15  5*2=10  5*1=5

    6*6=36  6*5=30  6*4=24  6*3=18  6*2=12  6*1=6

    7*7=49  7*6=42  7*5=35  7*4=28  7*3=21  7*2=14  7*1=7

    8*8=64  8*7=56  8*6=48  8*5=40  8*4=32  8*3=24  8*2=16  8*1=8

    9*9=81  9*8=72  9*7=63  9*6=54  9*5=45  9*4=36  9*3=27  9*2=18  9*1=9

    with a as

    (select distinct round(a.x + b.x) x, round(a.y + b.y) y

    from (select (sum(x) over(order by n)) x,

    round(sum(y) over(order by n)) y

    from (select n,

    cos(n / 30 * 3.1415926) * 2 x,

    sin(n / 30 * 3.1415926) y

    from (select rownum - 1 n

    from all_objects

    where rownum <= 30 + 30))) a,

    (select n,

    (sum(x) over(order by n)) x,

    round(sum(y) over(order by n)) y

    from (select n,

    cos(m / 3 * 3.1415926) * 2 * 15 x,

    sin(m / 3 * 3.1415926) * 15 y

    from (select case

    when rownum <= 2 then

    3

    when rownum = 3 then

    -2

    else

    -6

    end m,

    rownum - 1 n

    from all_objects

    where rownum <= 5))) b)

    select replace (sys_connect_by_path(point, '/'), '/', null) star  /*SQL 绘制奥运五环*/

    from (select b.y, b.x, decode(a.x, null, ' ', '*') point

    from a,

    (select *

    from (select rownum - 1 + (select min(x) from a) x

    from all_objects

    where rownum <= (select max(x) - min(x) + 1 from a)),

    (select rownum - 1 + (select min(y) from a) y

    from all_objects

    where rownum <= (select max(y) - min(y) + 1 from a))) b

    where a.x(+) = b.x

    and a.y(+) = b.y)

    where x = (select max(x) from a)

    start with x = (select min(x) from a)

    connect by y = prior y and x = prior x + 1;

    with a as                                             /*sql 绘制五角星*/

    (select distinct round(sum(x) over(order by n)) x,

    round(sum(y) over(order by n)) y

    from (select n,

    cos(trunc(n / 20) * (1 - 1 / 5) * 3.1415926) * 2 x,

    sin(trunc(n / 20) * (1 - 1 / 5) * 3.1415926) y

    from (select rownum - 1 n from all_objects where rownum <= 20 * 5)))

    select replace (sys_connect_by_path(point, '/'), '/', null) star

    from (select b.y, b.x, decode(a.x, null, ' ', '*') point

    from a,

    (select *

    from (select rownum - 1 + (select min(x) from a) x

    from all_objects

    where rownum <= (select max(x) - min(x) + 1 from a)),

    (select rownum - 1 + (select min(y) from a) y

    from all_objects

    where rownum <= (select max(y) - min(y) + 1 from a))) b

    where a.x(+) = b.x

    and a.y(+) = b.y)

    where x = (select max(x) from a)

    start with x = (select min(x) from a)

    connect by y = prior y and x = prior x + 1;

    SELECT LPAD(MONTH, 20 - (20 - LENGTH(MONTH)) / 2) MONTH, /*sql绘制年历*/

    "Sun",

    "Mon",

    "Tue",

    "Wed",

    "Thu",

    "Fri",

    "Sat"

    FROM (SELECT TO_CHAR(dt, 'fmMonthfm YYYY') MONTH,

    TO_CHAR(dt + 1, 'iw') week,

    MAX(DECODE(TO_CHAR(dt, 'd'),

    '1',

    LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Sun",

    MAX(DECODE(TO_CHAR(dt, 'd'),

    '2',

    LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Mon",

    MAX(DECODE(TO_CHAR(dt, 'd'),

    '3',

    LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Tue",

    MAX(DECODE(TO_CHAR(dt, 'd'),

    '4',

    LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Wed",

    MAX(DECODE(TO_CHAR(dt, 'd'),

    '5',

    LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Thu",

    MAX(DECODE(TO_CHAR(dt, 'd'),

    '6',

    LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Fri",

    MAX(DECODE(TO_CHAR(dt, 'd'),

    '7',

    LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Sat"

    FROM (SELECT TRUNC(SYSDATE, 'y') - 1 + ROWNUM dt

    FROM all_objects

    WHERE ROWNUM <= ADD_MONTHS(TRUNC(SYSDATE, 'y'), 12) -

    TRUNC(SYSDATE, 'y'))

    GROUP BY TO_CHAR(dt, 'fmMonthfm YYYY'), TO_CHAR(dt + 1, 'iw'))

    ORDER BY TO_DATE(MONTH, 'Month YYYY'), TO_NUMBER(week);

    MONTHSunMonTueWedThuFriSat

    1 1月 2010 3 4 5 6 7 8 9

    2 1月 201010111213141516

    展开全文
  • 筛法与质数

    2019-03-05 20:53:55
    给出一个自然数表(1,2,…,n),要求尽可能快的找出其中的质数,应该怎么做? 有两种思路:一种是遍历,一个个找质数,一种是去掉所有的合数.那么选择哪一种呢? 不管怎样,先来看看如何判定质数或者合数. 质数和合数的判定 ...

    给出一个自然数表(1,2,…,n),要求尽可能快的找出其中的质数,应该怎么做?
    有两种思路:一种是遍历,一个个找质数,一种是去掉所有的合数.那么选择哪一种呢?

    不管怎样,先来看看如何判定质数或者合数.

    质数和合数的判定

    质数和合数的定义在这不多讲.为判断是质数还是合数,最经典的方案就是遍历小于该数的所有整数(除了1),如果出现整除,那就不是.
    就像这样:

    while(i=2;i<N;i++)
    {
    	if(N%i==0)
    	{
    		return FALSE;
    	}
    }
    return TRUE;
    

    但这样需要扫描N-1次,对于大数而言要花相当多的时间,显然不是优解.那么在这里引入一个定理:
    theorem:xz x1ax使ax{theorem: }\\ \forall x\in\mathbb{z}且\ x是合数\\ \exists 1\le a\leq \sqrt{x} \\使得 a|x
    对该定理用反证法证明:
    proof:forx,(a,b),ab˙=x.(a!=0andb!=0)ifa&lt;x and b&lt;xab˙&lt;x.Q.E.D{proof:}\\ for 合数x,\\ \exists 整数对(a,b),a\dot b=x.(a!=0 and b!=0)\\ if a&lt; \sqrt{x}\ and\ b&lt; \sqrt{x}\\ \rightarrow a\dot b &lt; x\\ \therefore 原假设不成立.\\ Q.E.D
    所以现在提出第一个改进:
    只用扫描到x\sqrt{x}即可判断是否为质数.

    筛法

    结合上一部分,下面提出一个在自然数表中找出质数表的一个改进方法:

    1. x\sqrt{x}范围内找出质数;
    2. 清除这些质数的整数倍;
    3. 完成.

    &ThickSpace;&ThickSpace; 清除所有质数的整数倍\iff 清除所有合数
    二者是等价的吗?
    下面是解释:
    自然的,是一个整数的整数倍的数一定是合数.所以若清除了所有的合数必然清除所有质数的整数倍.由此必要性得证.
    下面是充分性:
    先引入一个定理:
    theorem:xN+x=i=1n ai,aiN+ai{theorem:}\\ \forall x \in\mathbb{N+}\\ x=\prod_{i=1}^{n}\ a_i,\\ a_i\in\mathbb{N+}且a_i是质数
    下面是证明:
    proof:a,1a˙,.b,i=1n mi,miN+mi,,.,,i=1n mi,miN+mik.{proof:} 对于质数a,可分解为1\dot a,成立.\\ 对于合数b,一定可以分解为\\ \prod_{i=1}^{n}\ m_i,m_i\in\mathbb{N+}\\ 对于m_i,若为质数,则分解停止.\\若为合数,则按照上一条,可以分解为 \prod_{i=1}^{n}\ m&#x27;_i,m&#x27;_i\in\mathbb{N+}\\ 以上过程均成立直到m^{k}_i均为质数.
    于是
    a is m is ma \forall a\ is\ 合数\\ \exists m\ is\ 质数\\ m|a\\
    充分性得证.

    那么:
    按照这个方法进行质数的筛选,有:

    for(a=1;a<=sqrt(x);a++)
    {
    	if(isPrime_number(a)==1)
    	{
    		for(b=2;ab<=x;b++)
    		{
    			remove(ab);
    		}
    	}
    	else
    	{
    		/*怎么会有else?*/
    	}
    }		
    

    就是这样了.

    展开全文
  • 埃拉托色尼筛法:求质数的方法其本质是...以下就是典型的例子:找出1000以内的所有质数.首先,把2的倍数全部划去,也就是说把2 * ( 2 到 500 )全部去掉,然后把3的倍数全部划去,也就是说把3 * ( 2 到 333 )全
  • 小白版本筛法

    2019-10-25 18:32:15
    怎么找出质数呢? 初阶版本的暴力版本大家都会,从1循环到sqrt(n)复杂度很高,为了提高效率,我们学习更快的筛选方法。 埃氏筛法 埃氏筛法的基本思想 :从2开始,将每个质数的倍数都标记成合数,以达到筛选素数的...
  • 题意:给你n,将1-n中的数字分成尽量少的集合,使得每个集合的和都为素数,...然后就贪心最大的,每一次拿最大的去填,感觉好像有问题,但是这种方法好像在哪里见过就没有多想直接上了,拍一些数据也居然过了。 然后
  • 举个简单的例子,很多安全加密算法也是利用的质数。我们想要利用素数去进行各种计算之前,总是要先找到素数。所以这就有了一个最简单也最不简单的问题,我们怎么样来寻找素数呢? 判断素数 寻
  • 举个简单的例子,很多安全加密算法也是利用的质数。我们想要利用素数去进行各种计算之前,总是要先找到素数。所以这就有了一个最简单也最不简单的问题,我们怎么样来寻找素数呢?判断素数寻找素数最朴素的方法当然是...
  • 如何储存1000000000大小的int型数据?比如说我要找出100000000000内所有质数找出质数应该存储在什么地方?数组肯定不行,动态申请也办不到似乎怎么了办?
  • 牛客 最长树链 图

    2019-12-28 15:23:02
    最长树链 题目链接 这道题让我明白了运气是实力的一部分 暴力出奇迹 ...就是枚举质数,但是枚举所有质数太多了,所以先找出所有点权的质因子,然后%这个质因子是0的点才能走,所以就是暴力? 但是我还...
  • 首先,要找出小于n的质数,也就是要分别判断n-1个数是不是质数。 那么要怎么判断一个数是不是质数? 比如一个数m,是不是要判断从1到m-1能不能被m整除? 那么这样要进行m-1次判断。 优化一下,其实可以只进行...
  • luogu P4626 一道水题 II

    2019-04-07 19:32:54
    背景: 数据范围好假。 题目传送门: ... 题意: 计算111到nnn的lcm\text{lcm}lcm。...考虑怎么计算lcm\text{lcm}lcm。...因此我们只需要找出所有质数的贡献,相乘就是结果。 对于一个质数aaa,我们显然想到求ax≤na^...
  • 2017.7.8~2017.7.9总结

    2017-07-09 21:37:48
    第一题什么诡异构造出质数,而且质数和加法我不到任何关系,一直没有想到怎么做 看到第二题时我就直接弃疗打暴力了,这个亦或起来再玩别的东西太麻烦了,但是弃疗这题花了我接近45分钟时间,如果有这时间去玩第三...
  • 不讲思路 (你懂的) ,直接写求max-min之后怎么做 判断是否为质数有很多方法,我呢,使用数组求解,因为这次的题目数据很水 ,关键代码如下: for(int i=2;i<=max-min;i++){ //注意一开始数组a的a[0]与a[1]要...
  • 素数判断

    千次阅读 2017-11-30 12:59:13
    在Raptor的某些问题中,会有判断素数或者找出某一区间范围内的素数,这样的问题比较多,因此本篇内容讲解怎么判断一个数是不是素数 定义:质数(prime number)又称素数,质数定义为在大于1的自然数中,除了1和它...
  • twitter面经

    2015-07-31 06:37:05
    twitter 店面 1. 前一百个质数. 一个一个check until找到100个, check的时候只需要from 2 to sqrt(n)....我说了怎么算但是没有给use case。。。他说工资啊,ceo的那么高,我们就用median不用m
  • 素数打表

    2018-08-27 21:42:07
     其实判断一个数是不是素数也非常简单,zhi'直接看他有几个因子就行了,一个fou循环就结束了,那么如果我让你找出100以内的素数,你怎么找,你首先会想到的是,那还不简单吗?两个fou循环就够了,那么如果我让你求...
  • 这题打比赛的时候只想到了质数怎么分配的,没有想到边的贡献怎么算,后来看了大佬的blog才知道的,Orz,其实你把一个树个顶点dfs一遍,设size[i]为该结点子树的大小,那么该点与其父亲结点的边的贡献为size[i]⋅(n...
  • 我们来看这个方程: a,b,p为常数且在int内。、p是质数。...就是一个点把[0,p-1]这个区间分成两半(一般中点),算前一半塞到hash表里面,再算后一半看看hash表里面有没有。 复杂度大概是上
  • UVa11388 - GCD LCM

    2017-10-24 21:25:45
    给出两个正整数G,L,找出两个数a,b,使得gcd(a,b)=G,lcm(a,b)=L 要求a尽量小分析: 假设我们已经知道了a和b的值 怎么求gcd,lcm呢(别告诉我是欧几里得算法)也就是说如果我们把G和L质因数分解了之后 每个...
  • 生活中从来不是想到即做到。 你买了一股基金,结果跌的没完没了,你该怎么整?...找出0-50之间的所有素数 什么是素数?,所谓素数就是只能被1和它本身整除的数字,(又名质数) #include <stdio.h> int
  • c组题怎么这么难啊 #A 美丽的 2 本题总分:5 分 问题描述 小蓝特别喜欢 222,今年是公元 202020202020 年,他特别高兴。 他很好奇,在公元 111 年到公元 202020202020 年(包含)中,有多少个年份的数位中包含...

空空如也

空空如也

1 2
收藏数 23
精华内容 9
关键字:

怎么找出质数