-
用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; }
-
判断质数和合数python代码_质数,非质数之Python
2020-12-15 14:14:58质数的定义:指在大于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
-
质数在mysql中怎么表达_利用SQL查找表中的质数(prime number)和完全数(perfect number)以及几个有趣的SQL...
2021-01-19 11:32:25之前在某次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次,对于大数而言要花相当多的时间,显然不是优解.那么在这里引入一个定理:
对该定理用反证法证明:
所以现在提出第一个改进:
只用扫描到即可判断是否为质数.筛法
结合上一部分,下面提出一个在自然数表中找出质数表的一个改进方法:
- 在范围内找出质数;
- 清除这些质数的整数倍;
- 完成.
二者是等价的吗?
下面是解释:
自然的,是一个整数的整数倍的数一定是合数.所以若清除了所有的合数必然清除所有质数的整数倍.由此必要性得证.
下面是充分性:
先引入一个定理:
下面是证明:
于是
充分性得证.那么:
按照这个方法进行质数的筛选,有:for(a=1;a<=sqrt(x);a++) { if(isPrime_number(a)==1) { for(b=2;ab<=x;b++) { remove(ab); } } else { /*怎么会有else?*/ } }
就是这样了.
-
埃拉托色尼筛法:求质数的方法
2010-04-12 00:06:00埃拉托色尼筛法:求质数的方法其本质是...以下就是典型的例子:找出1000以内的所有质数.首先,把2的倍数全部划去,也就是说把2 * ( 2 到 500 )全部去掉,然后把3的倍数全部划去,也就是说把3 * ( 2 到 333 )全 -
小白版本筛法
2019-10-25 18:32:15怎么找出质数呢? 初阶版本的暴力版本大家都会,从1循环到sqrt(n)复杂度很高,为了提高效率,我们学习更快的筛选方法。 埃氏筛法 埃氏筛法的基本思想 :从2开始,将每个质数的倍数都标记成合数,以达到筛选素数的... -
【GDOI2018模拟7.8】质数 乱搞+哥德巴赫猜想
2017-07-08 14:19:23题意:给你n,将1-n中的数字分成尽量少的集合,使得每个集合的和都为素数,...然后就贪心找最大的,每一次拿最大的去填,感觉好像有问题,但是这种方法好像在哪里见过就没有多想直接上了,拍一些数据也居然过了。 然后 -
一次找出范围内的所有素数,埃式筛法是什么神仙算法?
2020-06-07 09:44:09举个简单的例子,很多安全加密算法也是利用的质数。我们想要利用素数去进行各种计算之前,总是要先找到素数。所以这就有了一个最简单也最不简单的问题,我们怎么样来寻找素数呢? 判断素数 寻 -
c语言判断素数代码_一次找出范围内的所有素数,埃式筛法是什么神仙算法?...
2020-12-28 17:19:25举个简单的例子,很多安全加密算法也是利用的质数。我们想要利用素数去进行各种计算之前,总是要先找到素数。所以这就有了一个最简单也最不简单的问题,我们怎么样来寻找素数呢?判断素数寻找素数最朴素的方法当然是... -
c++中数据存储问题!!!
2016-09-24 12:50:47如何储存1000000000大小的int型数据?比如说我要找出100000000000内所有质数!找出的质数应该存储在什么地方?数组肯定不行,动态申请也办不到似乎怎么了办? -
牛客 最长树链 图
2019-12-28 15:23:02最长树链 题目链接 这道题让我明白了运气是实力的一部分 暴力出奇迹 ...就是枚举质数,但是枚举所有质数太多了,所以先找出所有点权的质因子,然后%这个质因子是0的点才能走,所以就是暴力? 但是我还... -
Leetcode 204shouxi Count Primes
2017-03-13 04:47:06首先,要找出小于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分钟时间,如果有这时间去玩第三... -
T1:【NOIP2008TG】笨小猴(word)
2020-05-02 16:15:48不讲思路 (你懂的) ,直接写求出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:05twitter 店面 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循环就够了,那么如果我让你求... -
Codeforces Round #665 (Div. 2) D-Maximum Distributed Tree(贪心+思维)
2020-08-24 00:58:18这题打比赛的时候只想到了质数怎么分配的,没有想到边的贡献怎么算,后来看了大佬的blog才知道的,Orz,其实你把一个树找个顶点dfs一遍,设size[i]为该结点子树的大小,那么该点与其父亲结点的边的贡献为size[i]⋅(n... -
高次同余笔记(一):baby-step-giant-step算法
2015-11-17 00:35:30我们来看这个方程: 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质因数分解了之后 每个... -
C++的break&&continue那些事儿
2021-01-05 22:50:32生活中从来不是想到即做到。 你买了一股基金,结果跌的没完没了,你该怎么整?...找出0-50之间的所有素数 什么是素数?,所谓素数就是只能被1和它本身整除的数字,(又名质数) #include <stdio.h> int -
第十一届蓝桥杯 2020年国赛真题 (Java 大学B组)
2020-11-15 15:01:22c组题怎么这么难找啊 #A 美丽的 2 本题总分:5 分 问题描述 小蓝特别喜欢 222,今年是公元 202020202020 年,他特别高兴。 他很好奇,在公元 111 年到公元 202020202020 年(包含)中,有多少个年份的数位中包含...