基础算法练习200题16、打印质数
基础算法练习200题16、打印质数
红目香薰
发布于 2022-11-29 11:27:34
发布于 2022-11-29 11:27:34
📋前言📋 💝博客：【红目香薰的博客_CSDN博客-计算机理论,2022年蓝桥杯,MySQL领域博主】💝 ✍本文由在下【红目香薰】原创，首发于CSDN✍ 🤗2022年最大愿望：【服务百万技术人次】🤗 💝专栏地址：【https://blog.csdn.net/feng8403000/category_11958599.html】💝
为了帮助很多想搞算法但又害怕自己搞不定的孩子们，老师付准备了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();
}
}
很多规律自己并不是很容易找到的，建议在网上查，你不可能记得天底下所有有用的公式与技巧，很多都是推演出来的，那么，如果有现成的正确的内容，并且能够解决实际问题，直接那来用就行，效率会更高一些，不要总想着你是天下无敌的。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-08-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号