当前位置:网站首页>Count prime [enumeration - > space for time]
Count prime [enumeration - > space for time]
2022-06-27 23:58:00 【REN_ Linsen】
Calculation 1-n The prime number of
Preface
For enumerations / Violence law , Both have high time complexity . The reason may be that the display conditions given by the title are not used / Implicit personalities that need to be mined , There may also be a lot of double counting , Need spatial records to ease time consumption .
One 、 Count prime
Two 、 enumeration -> Space for time
1、 Violence enumeration
// Count prime
public class CountPrimes {
/* target: Given a nonnegative integer n, Back to less than n All prime numbers of . What is prime number ? except 1 And itself , There are no other factors Greater than 1 The natural number of . */
// Violent solution
public int countPrimes(int n) {
// A special case , Special treatment .
if (n < 2) return 0;
// Determine whether each number is a prime number .
int ans = 1;// The first 2 count .
for (int i = 3; i < n; i++) if (isTrue(i)) ++ans;
return ans;
}
private boolean isTrue(int n) {
// prune , Just verify to sqrt(n) that will do , Mirror on both sides . Such as 2 * 4 == 8 == 4 * 2
int bound = (int) Math.sqrt(n);
for (int i = 2; i <= bound; i++) if (n % i == 0) return false;
return true;
}
}
2、 Space for time
class CountPrimes2 {
/* target: Given a nonnegative integer n, Back to less than n All prime numbers of . What is prime number ? except 1 And itself , There are no other factors Greater than 1 The natural number of . Violent solution timeout , If you can pick out the non prime numbers , Then the rest is prime , All non prime numbers are Prime numbers and prime numbers / Multiply nonprime numbers . Why is there no non prime number Multiply by these ? Because non prime numbers can be broken down into large and small numbers , And small numbers have all the following multiples The nonprime number of marks . Such as 8 == 2 * 4,8 * n == 2 * (4 * n) Each multiple of a prime number can be marked as Nonprime number , Then walk back , The unmarked ones are prime numbers , Then all multiples of the prime number ( In addition to the previously marked , So from i * i Start ) Marked as a non prime number . */
// Space for time , Record non prime numbers , Look for prime numbers .
public int countPrimes(int n) {
// A special case , Special treatment .
if (n < 2) return 0;
// Mark non prime numbers , Find the number of prime numbers .
boolean[] isNotPrim = new boolean[n];
int ans = 0;
for (int i = 2; i < n; i++) {
if (!isNotPrim[i]) {
// Not marked as non prime , Then it is a prime number .
++ans;
// Mark non prime numbers .
// from i * i Start , After all, it's my turn i-1 when , It has i,i+1,...
if (i < Math.sqrt(n)) for (int j = i * i; j < n; j += i) isNotPrim[j] = true;
}
}
return ans;
}
}
summary
1) Enumerate from violence , Go to space and change time ( Use the implicit features of the topic ).
reference
边栏推荐
- 计数质数[枚举 -> 空间换时间]
- 第 2 章 集成 MP
- Sentinel
- 一文剖析C语言函数
- virtualbox扩展动态磁盘大小的坑
- [AI application] detailed parameters of NVIDIA geforce RTX 3060
- webserver流程图——搞懂webserver各模块间调用关系
- 虽然TCGA数据库有33种癌症
- Mise en œuvre du pool de Threads: les sémaphores peuvent également être considérés comme de petites files d'attente
- 2022年PMP项目管理考试敏捷知识点(3)
猜你喜欢
Vivado FFT IP的使用说明
Zero foundation self-study SQL course | if function
[sword finger offer] 47 Maximum value of gifts
How to quote Chinese documents when writing a foreign language?
C WinForm reads the resources picture
webserver流程图——搞懂webserver各模块间调用关系
赛尔笔记|视频文本预训练简述
Cornernet understands from simple to profound
Safe, fuel-efficient and environment-friendly camel AGM start stop battery is full of charm
Transmitting and receiving antenna pattern
随机推荐
An analysis of C language functions
第 2 章 集成 MP
MySQL企业级参数调优实践分享
安全省油環保 駱駝AGM啟停電池魅力十足
What if Fiddler fails to listen to the interface
线程池实现:信号量也可以理解成小等待队列
企业架构师面试的100个问题
[PCL self study: Segmentation3] PCL based point cloud segmentation: region growth segmentation
MSP430F5529 单片机 读取 GY-906 红外温度传感器
支持删除,更新任意结点的优先级队列
Are the registered accounts of the top ten securities companies safe and risky?
Applet referer
Excel print settings public header
Feign通过自定义注解实现路径的转义
Swing UI container (I)
撰写外文时怎样引用中文文献?
通过中金证券经理的开户二维码开股票账户安全吗?还是去证券公司开户安全?
At the beginning of reading English literature, I would like to ask you how you should read it in the first place?
手把手教你移植 tinyriscv 到FPGA上
C language character pointer and string initialization