Sieve of Eratosthenes (素数筛选算法)
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″.
The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so (Ref Wiki).
Following is the algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:
- Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
- Initially, let p equal 2, the first prime number.
- Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
- Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.
When the algorithm terminates, all the numbers in the list that are not marked are prime.
Explanation with Example:
Let us take an example when n = 50. So we need to print all print numbers smaller than or equal to 50.
We create a list of all numbers from 2 to 50.
According to the algorithm we will mark all the numbers which are divisible by 2.
Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3.
We move to our next unmarked number 5 and mark all multiples of 5.
We continue this process and our final table will look like below:
So the prime numbers are the unmarked ones: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Related Practice Problem
http://www.practice.geeksforgeeks.org/problem-page.php?pid=425
Return two prime numbers
Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number. There are several combinations possible. Print only first such pair.
NOTE: A solution will always exist, read Goldbach’s conjecture.
Also, solve the problem in linear time complexity, i.e., O(n).
Input:
The first line contains T, the number of test cases. The following T lines consist of a number each, for which we'll find two prime numbers.
Note: The number would always be an even number.
Output:
For every test case print two prime numbers space separated, such that the smaller number appears first. Answer for each test case must be in a new line.
Constraints:
1 ≤ T ≤ 70
1 ≤ N ≤ 10000
Example:
Input:
5
74
1024
66
8
9990
Output:
3 71
3 1021
5 61
3 5
17 9973
import java.util.*;
import java.lang.*;
import java.io.*; class GFG { public static void func(int n) { boolean[] prime = new boolean[n+1];
for(int i=2; i<=n; ++i) {
prime[i] = true;
} for(int p=2; p*p<=n; ++p) {
if(prime[p]) {
for(int k=2*p; k<=n; k+=p) {
prime[k] = false;
}
}
} ArrayList<Integer> rs = new ArrayList<Integer> ();
for(int i=2; i<=n; ++i) {
if(prime[i]) {
rs.add(i);
}
} for(int i=0; i<rs.size(); ++i) {
int first = rs.get(i);
int second = n - first;
if(prime[first] && prime[second]) {
System.out.println(first + " " + second);
break;
}
}
} public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt(); for(int i=0; i<t; ++i) {
int n = in.nextInt();
func(n);
}
}
}
algorithm@ Sieve of Eratosthenes (素数筛选算法) & Related Problem (Return two prime numbers )的更多相关文章
-
Algorithm: Sieve of Eratosthenes
寻找比n小的所有质数的方法. 2是质数, 2*i都是质数,同样3是质数,3*i也都是质数 代码如下 int n; vector<, true); prime[] = prime[] = fals ...
-
UVa 1210 (高效算法设计) Sum of Consecutive Prime Numbers
题意: 给出n,求把n写成若干个连续素数之和的方案数. 分析: 这道题非常类似大白书P48的例21,上面详细讲了如何从一个O(n3)的算法优化到O(n2)再到O(nlogn),最后到O(n)的神一般的 ...
-
使用埃拉托色尼筛选法(the Sieve of Eratosthenes)在一定范围内求素数及反素数(Emirp)
Programming 1.3 In this problem, you'll be asked to find all the prime numbers from 1 to 1000. Prime ...
-
埃拉托色尼筛法(Sieve of Eratosthenes)求素数。
埃拉托色尼筛法(Sieve of Eratosthenes)是一种用来求所有小于N的素数的方法.从建立一个整数2~N的表着手,寻找i? 的整数,编程实现此算法,并讨论运算时间. 由于是通过删除来实现, ...
-
[原]素数筛法【Sieve Of Eratosthenes + Sieve Of Euler】
拖了有段时间,今天来总结下两个常用的素数筛法: 1.sieve of Eratosthenes[埃氏筛法] 这是最简单朴素的素数筛法了,根据wikipedia,时间复杂度为 ,空间复杂度为O(n). ...
-
[Algorithm] Finding Prime numbers - Sieve of Eratosthenes
Given a number N, the output should be the all the prime numbers which is less than N. The solution ...
-
素数筛选法(prime seive)
素数筛选法比较有名的,较常用的是Sieve of Eratosthenes,为古希腊数学家埃拉托色尼(Eratosthenes 274B.C.-194B.C.)提出的一种筛选法.详细步骤及图示讲解,还 ...
-
*大学(新大)OJ xju 1009: 一带一路 prim求最短路径+O(n)素数筛选
1009: 一带一路 时间限制: 1 Sec 内存限制: 128 MB 题目描述 一带一路是去去年习大大提出来的建设“新丝绸之路经济带”和“21世纪海上丝绸之路”的战略构想.其中就包括我们*乌鲁木 ...
-
“计数质数”问题的常规思路和Sieve of Eratosthenes算法分析
题目描述 题目来源于 LeetCode 204.计数质数,简单来讲就是求"不超过整数 n 的所有素数个数". 常规思路 一般来讲,我们会先写一个判断 a 是否为素数的 isPrim ...
随机推荐
-
yii2框架安装
注意:先把php.ini里面的php_openssl.dll扩展打开 1.下载yii2框架的文件包yii-advanced-app-2.0.7 2.打开路径为advanced下面的init.bat ...
-
Project Euler 89:Roman numerals 罗马数字
Roman numerals For a number written in Roman numerals to be considered valid there are basic rules w ...
-
基于Jquery 的 Chart
Flot Flot一个纯javascript绘画库,基于jQuery开发.它能够在客户端根据任何数据集快速生成图片.目前只能绘制线状图和柱状. Flot jQuery jQchart 基于C ...
-
drop、truncate和delete的区别
TRUNCATE TABLE 在功能上与不带 WHERE 子句的 DELETE 语句相同:二者均删除表中的全部行.但 TRUNCATE TABLE 比 DELETE 速度快,且使用的系统和事务日志资源 ...
-
canvas高级篇(转载)移动元素
本文转载在http://bbs.blueidea.com/thread-2979405-1-1.html 哈哈哈,好骚气!终于解决了我的需求.可以移动canvas内的多个元素 <!DOCTYPE ...
-
剑指Offer 42. 和为S的两个数字 (其他)
题目描述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的. 输出描述: 对应每个测试案例,输出两个数,小的先输出. 题目 ...
-
Layui_HDFS目录(上传,下载,删除,分页,下级目录,键盘控制返回上一页)
注:转载请署名 一.实体 package com.ebd.application.modules.fileManage.pojo; public class FilesOrDirs { private ...
-
C++学习笔记40:进程应用
进程创建 system()函数:用于在程序中执行一条命令 如果shell不能运行,返回127,如果发生其他错误返回-1: 例子:int ret_val = system(“ls -l /”); for ...
-
SourceInsight 4重启之后文件变只读无法编辑
SourceInsight4.0在导入代码后,用起来没问题,第二天,再开启sourceInsight,结果所有文件变成只读了,不能编辑,标签前面也有了叹号. 百度一下,有人说是版本控制的问题,但是sv ...
-
DB2自增长ID
建议类似的应用采用sequence对象,将来的应用维护和数据迁移会很方便.考虑的因素较少. 对于序列可以使用nextval和prevval来获得下一个和上一个值:CREATE SEQUENCE seq ...