基础算法练习200题16、打印质数
【摘要】 编辑📋前言📋💝博客：【红目香薰的博客_CSDN博客-计算机理论,2022年蓝桥杯,MySQL领域博主】💝✍本文由在下【红目香薰】原创，首发于CSDN✍🤗2022年最大愿望：【服务百万技术人次】🤗💝专栏地址：【https://blog.csdn.net/feng8403000/category_11958599.html】💝 为了帮助很多想搞算法但又害怕自己搞...
📋前言📋
💝博客：【红目香薰的博客_CSDN博客-计算机理论,2022年蓝桥杯,MySQL领域博主】💝✍本文由在下【红目香薰】原创，首发于CSDN✍
🤗2022年最大愿望：【服务百万技术人次】🤗
💝专栏地址：【】💝
为了帮助很多想搞算法但又害怕自己搞不定的孩子们，老师付准备了200个入门的逻辑练习题，在这200个逻辑练习题下可以加强你们的基础算法能力，以次为基础当面对正式的算法题目的时候可以得心应手的面对。
题目：
输入一个数n，输出1-n(不包含n)的所有质数。
输入样例：5
输出样例：
2
3
暴力；输出：
package com.item.action;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
/**
*
* @author hongmuxiangxun 红目香薰 付文龙 老师付 laoshifu
*
*/
public class demo16 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
sc.close();
// 向文本输出流打印对象
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
for (int i = 2; i < num; i++) {
boolean isf = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
isf = false;
break;
}
}
if (isf) {
pw.println(i);
}
}
pw.close();
}
}
时间计算（测试数据10W）：
package com.item.action;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
/**
*
* @author hongmuxiangxun 红目香薰 付文龙 老师付 laoshifu
*
*/
public class demo16 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
sc.close();
long start = System.currentTimeMillis();
// 向文本输出流打印对象
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
for (int i = 2; i < num; i++) {
boolean isf = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
isf = false;
break;
}
}
if (isf) {
pw.println(i);
}
}
long end = System.currentTimeMillis();
pw.println("消耗时间:"+(end-start)+"毫秒");
pw.close();
}
}
优化（测试数据10W）：
只要把循环一直从2尝试到根号x就可以，可以发现，一个数的两个因数中，毕然有一个小于等于根号x，一个大于等于根号x。
例如100的因数有：1和100，2和50，4和25，5和20，10和10。所以只要从2尝试到根号x，如果都没有被整除，就是素数，否则就不是。
package com.item.action;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
/**
*
* @author hongmuxiangxun 红目香薰 付文龙 老师付 laoshifu
*
*/
public class demo16 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
sc.close();
long start = System.currentTimeMillis();
// 向文本输出流打印对象
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
for (int i = 2; i < num; i++) {
boolean isf = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
isf = false;
break;
}
}
if (isf) {
pw.println(i);
}
}
long end = System.currentTimeMillis();
pw.println("消耗时间:"+(end-start)+"毫秒");
pw.close();
}
}
很多规律自己并不是很容易找到的，建议在网上查，你不可能记得天底下所有有用的公式与技巧，很多都是推演出来的，那么，如果有现成的正确的内容，并且能够解决实际问题，直接那来用就行，效率会更高一些，不要总想着你是天下无敌的。
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）