public class Test {
//定义第一个静态整数类型的集合用于存储最终的数字结果
private static ArrayList<Integer> integers = new ArrayList<>();
//定义第二个静态整数类型的集合用于存储最终的数字结果
private static ArrayList<Integer> integers2 = new ArrayList<>();
//先创建一个静态键盘录入扫描的对象
private static Scanner scanner = new Scanner(System.in);
//定义主方法
public static void main(String[] args) {
//定义一个死循环
while (true){
//提示用户输入，并接收
System.out.println("请输入小写字母a或b或c或d");
String s = scanner.nextLine();
//用switch单只匹配
switch (s){
//当输入的值是“a”时，为基数
case "a":
//调用方法
ArrayList<Integer> cardinalNumber = isCardinalNumber();
//打印集合
System.out.println("100以内的基数有："+cardinalNumber);
break;
//当输入的值是“b”时，为偶数
case "b":
//调用方法
ArrayList<Integer> evenNumbers = isEvenNumbers();
//打印集合
System.out.println("100以内的偶数有："+evenNumbers);
break;
//当输入的值是“c”时，为质数
case "c":
//调用方法
ArrayList<Integer> primeNumber = isPrimeNumber();
//打印集合
System.out.println("100以内的质数有："+primeNumber);
break;
//当输入的值是“d”时，为合数
case "d":
//调用方法
ArrayList<Integer> totalNumber = isTotalNumber();
//打印集合
System.out.println("100以内的合数有："+totalNumber);
break;
//当输入的值是“ac”时，为即是基数又是质数
case "ac":
//调用方法
ArrayList<Integer> cardinalNumberAndPrimeNumber = ();
//打印集合
System.out.println("100以内的即是基数又是质数有："+cardinalNumberAndPrimeNumber);
break;
default:
System.out.println("您只可以输入一下小写字母：a，b，c，d，ac");
}
}
}
/**
* 封装方法，判断是否是基数
* @return
*/
public static ArrayList<Integer> isCardinalNumber(){
//先清空集合
integers.clear();
//定义for循环遍历到所有的100以内的整数
for (int i = 0; i <= 100; i++) {
//判断出所有的基数并保存到集合中
if (i % 2 != 0){
integers.add(i);
}
}
return integers;
}
/**
* 封装方法：是否是偶数
* @return
*/
public static ArrayList<Integer> isEvenNumbers(){
//先清空集合
integers.clear();
//定义for循环遍历到所有的100以内的整数
for (int i = 0; i <= 100; i++) {
//判断出所有的偶数并保存到集合中
if (i % 2 == 0)integers.add(i);
}
return integers;
}
/**
* 封装方法：是否是质数
* @return
*/
public static ArrayList<Integer> isPrimeNumber(){
//先清空集合
integers.clear();
//定义外循环遍历到2到100的数，1直接跳过
for(int i = 2 ; i <= 100;i++) {
//1、定义一个标记
boolean flag = true;
//定义内循环，Math.squart()取i平方根，对其它数取余能整除就不是质数。固定算法
for(int j = 2; j <= (int)Math.sqrt(i); j++) {
if(i % j == 0) {
//2、更改标记
flag = false;
break;
}
}
//3、得结论
if(flag) {
integers.add(i);
}
}
return integers;
}
/**
* 封装方法：是否是合数
* @return
*/
public static ArrayList<Integer> isTotalNumber(){
//先清空集合
integers.clear();
//定义外循环遍历到2到100的数，1直接跳过
for(int i = 2 ; i <= 100;i++) {
//1、定义标记
boolean flag = false;
//定义内循环。能被1或自身或其它数整除就是合数
for(int j = 2; j < i; j++) {
if(i % j == 0) {
//2、更改标记
flag = true;
break;
}
}
//3、得结论
if(flag) {
integers.add(i);
}
}
return integers;
}
/**
* 封装方法：即是基数又是质数
* @return
*/
public static ArrayList<Integer> (){
//先选出基数
ArrayList<Integer> cardinalNumber = isCardinalNumber();
//再从集合中选出质数
//定义外循环遍历集合
for (Integer integer : cardinalNumber) {
//1、定义一个标记
boolean flag = true;
//定义内循环，Math.squart()取i平方根，对其它数取余能整除就不是质数。固定算法
for(int j = 2; j <= (int)Math.sqrt(integer); j++) {
if(integer % j == 0) {
//2、更改标记
flag = false;
break;
}
}
//3、得结论
if(flag) {
integers2.add(integer);
}
}
return integers2;
}
//最后就是不用说了吧。自己组合。从已有的集合中选数字就行。这样能避免复杂的判断出现的错误
}
2. java程序1到200的质数。代码如下
一个好的算法，要经的起推敲，不要只求结果
importjava.util.ArrayList;
importjava.util.List;
publicclassPrimes{
publicstaticvoidmain(String[]args){
//求素数
List<Integer>primes=getPrimes(200);
//输出结果
for(inti=0;i<primes.size();i++){
Integerprime=primes.get(i);
System.out.printf("%8d",prime);
if(i%10==9){
System.out.println();
}
}
}
/**
*求n以内的所有素数
*
*@paramn
*范围
*
*@returnn以内的所有素数
*/
privatestaticList<Integer>getPrimes(intn){
List<Integer>result=newArrayList<Integer>();
result.add(2);
for(inti=3;i<=n;i+=2){
if(!divisible(i,result)){
result.add(i);
}
}
returnresult;
}
/**
*判断n是否能被整除
*
*@paramn
*要判断的数字
*@paramprimes
*包含素数的列表
*
*@return如果n能被primes中任何一个整除，则返回true。
*/
privatestaticbooleandivisible(intn,List<Integer>primes){
for(Integerprime:primes){
if(n%prime==0){
returntrue;
}
}
returnfalse;
}
}
3. 要求用JAVA编程输出3---100以间的所有素数。
最有效率的算法，请看下面
package number;
import java.util.HashMap;
import java.util.Map;
/**
* 查找小于某个数的所有素数。
* 最简单的方法就是试除法，将该数N用小于等于N的平方根的所有素数去试除，若均无法整除，则N为素数。
* @author Owner
*
*/
public class CheckPrime {
/**
* 用来保存所有已查找到的素数，为后面验证N为素数时提供小于N的平方根的素数。
*/
private static Map<String, CheckPrime> primeMap = new HashMap<String, CheckPrime>();
private int value;
private boolean isPrime = true;
public boolean isPrime(){
if(value < 4)
// 如果小于4，则一定为素数。
isPrime = true;
else {
// 获取小于等于平方根的最小正整数。
int sqrtValue = Integer.parseInt(String.valueOf(Math.sqrt((double)value)).replaceAll("\\..*", ""));
for(int i = sqrtValue; i > 1; i --){
// 获取下雨平方根的所有素数进行判断
CheckPrime subPrime = primeMap.get(i + "");
if(subPrime != null){
if(this.value % subPrime.value == 0){
// 如果能被某个素数整除，则为质数，跳出循环
isPrime = false;
break;
}
}
}
}
return isPrime;
}
public static void savePrime(int primeValue){
CheckPrime prime = new CheckPrime();
prime.value = primeValue;
primeMap.put("" + primeValue, prime);
System.out.println(primeValue);
}
public static void main(String[] args) {
for(int i = 2; i < 100; i ++){
CheckPrime prime = new CheckPrime();
prime.value = i;
if(prime.isPrime())
CheckPrime.savePrime(i);
}
}
}
4. JAVA:输出1-100之间的所有质数，写出一种可用算法步骤，开头已给出
从1到50循环
然后让每一个数循环除23456789
如果这8次除的结果都不是整数或者=1，那么为质数
如果这8次除的结果有整数且不等于1，那么为合数，跳出此次循环
进行下一循环
算法不是最好，不过简单易懂
希望有帮助
5. 去哪儿网java开发面试经验牛客
以下是某位求职者面经，仅供参考：
一面:
1.自我介绍
2.直接上手红黑树和平衡二叉树区别
3.红黑树的旋转
2node节点插入和3node节点插入时候旋转的情况 简述伪代码
4.问项目情况。大概半小时 5.concurrenthashmap
结构分析。 删除和获取操作过程描述。就是segment. Entry.
除了value 为volatile 其余都是final.
删除和获取操作等等。例如：删除操作是将entry要删除的节点的前半部分链表进行复制，并指向当前删除节点的后面节点。（因为next是final的，不可以进行修改，只有entry的表头可以修改）
不详述了。
6.索引的优缺点 什么时候索引不起作用？ 在什么地方可以使用索引？
7.jvm
多态原理。invokestatic invokeinterface
等指令。常量池中的符号引用 找到直接引用。在堆中找到实例对象，获取到偏移量，由偏移量在方法表中指出调用的具体方法。接口是在方法表中进行扫描）等等扯了半天
8.os: 页面调度算法 几种 分别说一下 LRU FIFO 最佳适应算法
9.内存管理： 固定分区 动态分区 段 页 都讲讲 （哈哈）
10.自己实现一下LRU算法
8.怎么学习。看过什么书
二面：
1.自我介绍
2.项目中与app移动端 的json格式设计
3.hashmap的缺点 具体提现在哪里？
4.Collections.sort()
的原理---本质上调用的是Arrays.sort() 内部是 使用的归并排序 接着写了一下归并（辅助数组的归并，和手摇算法的归并）
5.一个字符串数组，现给定一个string去进行找出对应的数组中字符串的下标 （可以有容错，但两字符串长度必须一致，容错为2）
例如：
["hello","hj","abc"]
key=“hellg" 返回下角标0
6.jvm参数调优 jvm堆的大小调优
MaxTureningShelod newratio -xxs -xxm -persize
7.图的 prime
算法
kruskal
算法
dijkstra算法 解决什么问题？ 分别写一下
伪代码
8.设计模式： 单例模式（懒汉饿汉） 工厂方法模式 观察者模式 责任链模式
9.项目 又问了一些
10.平时怎么学习？
三面：
1.自我介绍
2.自己优缺点
3.目前有几个offer
4.工作地点要求
5.在校实验室做项目，你认为最大的收获是什么
6.评价一下自己的大学生活
7.讲了一下福利 之类的
现场书面offer没了，所以只好等等邮寄，不过还好给了一个布偶纪念品
6. java教师工作量计算法
/**
* 我写了一个 希望 有用
*
* 如果 哪位高手 有兴趣
* 帮忙 实现 一下 Teacher 类中的 private void checkClassRepeat() 方法 感谢！！
*/
==================================第一个类 TypeValue
package org.wood.teacher;
/**
* 创建 各种系数常量
* @author Administrator
*
*/
public interface TypeValue {
/**
* 理论课系数 1.2
*/
double COURSE_TYPE_THEORY_VALUE = 1.2;
/**
* 实训课系数 0.8
*/
double COURSE_TYPE_PRACTISE_VALUE = 0.8;
/**
* 班级系数
*/
/**
* 小于40人 系数1
*/
double CLASS_TYPE_STUDENT_NUMBER_UNDER_40_VALUE = 1.0;
/**
* 大于等于40人且小于80人 系数1.1
*/
double CLASS_TYPE_STUDENT_NUMBER_BETWEEN_40_AND_80_VALUE = 1.1;
/**
* 大于等于80人且小于100人 系数1.2
*/
double CLASS_TYPE_STUDENT_NUMBER_BETWEEN_80_AND_100_VALUE = 1.2;
/**
* 大于等于100人 系数1.3
*/
double CLASS_TYPE_STUDENT_NUMBER_ABOVE_100_VALUE = 1.3;
/**
* 职称系数
*/
/**
* 助教 系数1
*/
double LEVEL_TYPE_ASISITANT_VALUE = 1.0;
/**
* 讲师 系数1.2
*/
double LEVEL_TYPE_DOCENT_VALUE = 1.2;
/**
* 副教授 系数1.5
*/
double LEVEL_TYPE_ASSOCIATE_PROFESSOR_VALUE = 1.5;
/**
* 正教授 系数2
*/
double LEVEL_TYPE_PROFESSOR_VALUE = 2.0;
/**
* 理论课重复系数
*/
/**
* 重复课系数
*/
double REPEAT_COURSE_VALUE = 0.8;
/**
* 非重复课 系数
*/
double UNREPEAT_COURSE_VALUE = 1;
}
==================================第二个类 Class类
package org.wood.teacher;
/**
* 班级类 包含
* 班级号 classId
* 班级课程类别(courseName)：如java，c++，.net或其他
* 班级人数(studentNumber)
* 班级理论课时间(theoryTime)
* 班级实训（实践）课时间(practiseTime)
* 班级是不是重复的 repeat(如果是重复的，计算该班级的工作量时，使用的系数与重复的不一样)
* repeat属性，比较特殊，需要在统计该班的工作量之前，确定该班是否是重复了。
* repeat=true; 重复的
* repeat=false; 班级非重复的
*
* 核心方法 calculateClassWorkload
* 该方法 用来计算 带此班的老师的工作量，有一个参数，就是老师的职称系数。
*
* 如：30(理论课天数)*1.2（理论课系数）*1.1（60人,学生人数系数）*1.2（职称系数）*1(非重复系数，人多的班级) + 10(实践天数)*0.8（实践课系数）*1.1（60人，学生人数系数）*1.2（职称系数）
*
* 30(理论课天数)*1.2（理论课系数）*1.1（60人,学生人数系数）*1.2（职称系数）*0.8(重复系数，人少的班级) + 10(实践天数)*0.8（实践课系数）*1.1（60人，学生人数系数）*1.2（职称系数）
* @author Administrator
*
*/
public class Class {
private int classId;
// 班级课程类别
private String courseName;
// 班级人数
private int studentNumber;
// 班级理论课时间
private int theoryTime;
// 班级实训（实践）课时间
private int practiseTime;
private boolean repeat;
public Class() {
super();
}
public Class(int classId, String courseName, int studentNumber,
int theoryTime, int practiseTime) {
super();
this.classId = classId;
this.courseName = courseName;
this.studentNumber = studentNumber;
this.theoryTime = theoryTime;
this.practiseTime = practiseTime;
}
/**
* 计算班级工作量 参数 为 老师的 职称系数
*
* @param teacherLevlValue(参数为 该老师的 职称的系数）
* @return
*/
public double calculateClassWorkload(double teacherLevelValue) {
/**
* 判断是否是重复的课程
*/
if (this.repeat) {
System.out.println(this.courseName+" "+this.classId+"班，重复了！");
System.out.println(
this.theoryTime+" * "
+ TypeValue.COURSE_TYPE_THEORY_VALUE+" * "
+()+" * "
+teacherLevelValue+" * "
+TypeValue.REPEAT_COURSE_VALUE +"(重复系数) + "
+this.practiseTime+" * "
+ TypeValue.COURSE_TYPE_PRACTISE_VALUE+" * "
+()+" * "
+teacherLevelValue);
/**
* 重复的班级 工作量算法
* 30(理论课天数)*1.2（理论课系数）*1.1（60人,学生人数系数）*1.2（职称系数）*0.8(重复系数，人少的班级) + 10(实践天数)*0.8（实践课系数）*1.1（60人，学生人数系数）*1.2（职称系数）
*/
return this.theoryTime
* TypeValue.COURSE_TYPE_THEORY_VALUE
* ()
* teacherLevelValue
* TypeValue.REPEAT_COURSE_VALUE
+ this.practiseTime
* TypeValue.COURSE_TYPE_PRACTISE_VALUE
* ()
* teacherLevelValue;
} else {
// System.out.println(this.classId+"班，非重复！");
System.out.println(
this.theoryTime+" * "
+ TypeValue.COURSE_TYPE_THEORY_VALUE+" * "
+()+" * "
+teacherLevelValue+" * "
+TypeValue.UNREPEAT_COURSE_VALUE +"(非重复系数) + "
+this.practiseTime+" * "
+ TypeValue.COURSE_TYPE_PRACTISE_VALUE+" * "
+()+" * "
+teacherLevelValue);
/**
* 非重复的班级的 工作量的算法
* 30(理论课天数)*1.2（理论课系数）*1.1（60人,学生人数系数）*1.2（职称系数）*1(非重复系数，人多的班级) + 10(实践天数)*0.8（实践课系数）*1.1（60人，学生人数系数）*1.2（职称系数）
*/
return this.theoryTime
* TypeValue.COURSE_TYPE_THEORY_VALUE
* ()
* teacherLevelValue
* TypeValue.UNREPEAT_COURSE_VALUE
+ this.practiseTime
* TypeValue.COURSE_TYPE_PRACTISE_VALUE
* ()
* teacherLevelValue;
}
}
/**
* 获取班级 人数系数
*
* @return
*/
private double () {
if (this.studentNumber > 0 && this.studentNumber < 40) {
return TypeValue.CLASS_TYPE_STUDENT_NUMBER_UNDER_40_VALUE;
} else if (this.studentNumber >= 40 && this.studentNumber < 80) {
return TypeValue.CLASS_TYPE_STUDENT_NUMBER_BETWEEN_40_AND_80_VALUE;
} else if (this.studentNumber >= 80 && this.studentNumber < 100) {
return TypeValue.CLASS_TYPE_STUDENT_NUMBER_BETWEEN_80_AND_100_VALUE;
} else if (this.studentNumber >= 100) {
return TypeValue.CLASS_TYPE_STUDENT_NUMBER_ABOVE_100_VALUE;
}
return -1;
}
public int getClassId() {
return classId;
}
public void setClassId(int classId) {
this.classId = classId;
}
public String getCourseName() {
return courseName;
}
public void setCourseName(String courseName) {
this.courseName = courseName;
}
public int getStudentNumber() {
return studentNumber;
}
public void setStudentNumber(int studentNumber) {
this.studentNumber = studentNumber;
}
public int getTheoryTime() {
return theoryTime;
}
public void setTheoryTime(int theoryTime) {
this.theoryTime = theoryTime;
}
public int getPractiseTime() {
return practiseTime;
}
public void setPractiseTime(int practiseTime) {
this.practiseTime = practiseTime;
}
public boolean isRepeat() {
return repeat;
}
public void setRepeat(boolean repeat) {
this.repeat = repeat;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((courseName == null) ? 0 : courseName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Class other = (Class) obj;
if (courseName == null) {
if (other.courseName != null)
return false;
} else if (!courseName.equals(other.courseName))
return false;
return true;
}
}
==================================第三个类 Teacher类
package org.wood.teacher;
import java.util.ArrayList;
import java.util.List;
/**
* 教师类 包含教室的 姓名，职称（级别）信息
*
* 核心方法 计算该教师的工作量(多个班级的工作量的和) calculateWorkload();
*
* @author Administrator
*
*/
public class Teacher {
/**
* 姓名
*/
private String name;
/**
* 职称/级别 助教、讲师、副教授、正教授
*/
private String level;
/**
* 老师 所带领的班级的集合
*
*/
private List<Class> classes = new ArrayList<Class>();
public Teacher() {
super();
}
public Teacher(String name, String level) {
super();
this.name = name;
this.level = level;
}
/**
* addClass(Class clas) 添加 老师带的班级 到 老师带班集合
*
* @param clas
*/
public void addClass(Class clas) {
this.classes.add(clas);
}
/**
* 计算教师的工作量(workload)
*
* @return
*/
public double calculateWorkload() {
/**
* 获取教师的级别系数
*/
double levlValue = getTeacherLevlValue();
System.out.println("职称系数："+levlValue);
/**
* 检测 教师 所带领的 班级
* 如果 有班级是 重复的，将人数最少的班级 的重复属性 赋值为 true
*/
checkClassRepeat();
/**
* 计算 工作量
* 结合 教师的 职称
*/
double sum=getSum(levlValue);
return sum;
}
private double getSum(double levlValue) {
double sum=0.0;
for(Class c:this.classes){
sum+=c.calculateClassWorkload(levlValue);
System.out.println("SUM:---->"+sum);
}
return sum;
}
/**
* 检测 教师 所带领的 班级
* 如果 有班级是 重复的，将人数最少的班级 的重复属性 赋值为 true
*/
private void checkClassRepeat() {
/**
* 此方法 没有实现，请高手 实现
*
* 我的想法是遍历 List<Class> classes 集合，比较集合中的对象，
* 如果有对象是相同的（我重写了Class的equals()方法，只要课程名相同，就表示两个班相同）
* 则将 班级人数少的班级的重复 属性 赋值为true(默认为false)---->计算班级的工作量是用到 该属性 做判断
*
* 我遇到的问题是，如果一个老师 带的重复的班级 有3个或三个以上(如:3个java班)，我的逻辑就有点乱了，没理过来
* 请高手帮忙!!
*
* 现在只能 手动地设置 某个班级 为重复的，从而进行计算
*/
}
/**
* 获取教师的 职称系数方法
* 通过 教师的 职称 确定的 教师的 职称系数
* @return
*/
private double getTeacherLevlValue() {
// 助教、讲师、副教授、正教授
if ("助教".equals(this.level)) {
return TypeValue.LEVEL_TYPE_ASISITANT_VALUE;
} else if ("讲师".equals(this.level)) {
return TypeValue.LEVEL_TYPE_DOCENT_VALUE;
} else if ("副教授".equals(this.level)) {
return TypeValue.LEVEL_TYPE_ASSOCIATE_PROFESSOR_VALUE;
} else if ("正教授".equals(this.level)) {
return TypeValue.LEVEL_TYPE_PROFESSOR_VALUE;
}
return -1;
}
/**
* 计算教师的收入
*
* @param perWorkloadPrice(单价)
* @return
*/
public double calculateIncome(double perWorkloadPrice) {
return calculateWorkload()*perWorkloadPrice;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getLevel() {
return level;
}
public void setLevel(String level) {
this.level = level;
}
public List<Class> getClasses() {
return classes;
}
public void setClasses(List<Class> classes) {
this.classes = classes;
}
}
==================================第四个类 测试类 TestCal类
package org.wood.teacher;
public class TestCal {
public static void main(String[] args) {
/**
* 职称/级别 助教、讲师、副教授、正教授
*/
Teacher teacher=new Teacher("张三","讲师");
/**
* 构建 班级1 对象
* 班级2 java课 60人 30天理论 10天实践
*/
Class class01=new Class(1,"java",35,30,10);
class01.setRepeat(true);
/**
* 构建 班级2 对象
* 班级2 java课 60人 30天理论 10天实践
*/
Class class02=new Class(2,"java",60,30,10);
class02.setRepeat(false);
/**
* 将1,2班 添加到教室 带班列表
*/
teacher.addClass(class01);
teacher.addClass(class02);
/**
* 计算工作量
*/
double result=teacher.calculateWorkload();
System.out.println("R:"+result);
/**
* 单个班级 java02 班 测试数据
* 30(理论课天数)*1.2（理论课系数）*1.1（60人,学生人数系数）*1.2（职称系数）*1(非重复系数，人多的班级) + 10(实践天数)*0.8（实践课系数）*1.1（60人，学生人数系数）*1.2（职称系数）
* 理论数据： 30 * 1.2 * 1.1 * 1.2 * 1 + 10 * 0.8 * 1.1 * 1.2 =58.08
* 程序数据： 30 * 1.2 * 1.1 * 1.2 * 1.0 + 10 * 0.8 * 1.1 * 1.2 =58.080000000000005(double类型数据不精确存储)
*/
/**
* 两个班级 java01 java02 班 共同 测试数据
* java 1班，重复了！
* 30 * 1.2 * 1.0 * 1.2 * 0.8(重复系数) + 10 * 0.8 * 1.0 * 1.2
*
* java 2班
* 30 * 1.2 * 1.1 * 1.2 * 1.0(非重复系数) + 10 * 0.8 * 1.1 * 1.2
*
* 程序数据结果：R:102.24000000000001
*
*/
}
}
/**
*
*实现了Teacher 类中的 private void checkClassRepeat() 方法 就可以
*自动判断 哪一个 班级是重复的
* 但是 现在 我未能实现此方法
* 只能 像测试类中的 那样， 手动地 设置 该班级 是否是重复班级
*/
7. java代码求指点,只是计算100--200内的素数,却怎么都弄不出来
只能被1和它自己本身所整除的数成为素数或质数，以下为三种求N以内素数的算法。
一、从1至N全部遍历，当这个数只能被1和n整除它就是素数。
/**
* 打印自然数n以内的素数
*/
public void printPrime(int n){
//是否为质数
boolean isPrime;
for (int i = 1; i <= n; i++) {
isPrime = true;
for (int j = 2; j < i; j++) {
//若能除尽，则不为质数
if ((i % j) == 0) {
isPrime = false;
break;
}
}
//如果是质数，则打印
if (isPrime) {
System.out.println(i);
}
}
}
二、筛数法求素数
筛数法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。
public void printPrimes(int n){
//定义arr数组来表示筛选出来的素数
boolean arr[] = new boolean[n];
//arr数组坐标i不是素数的话就令arr[i]=false
for(int k=2;k<N;K++){< p>
if(!arr[k]){
for(int i=2*k;i< p>
arr[i] =false;
}
}
}
//把求的素数放入数组a中。
for(int i=1;i<N;I++){< p>
if(arr[i]){
System.out.println(i);
}
}
}
三、6N±1法求素数
任何一个自然数，总可以表示成为如下的形式之一：
6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以，除了2和3之外，所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析，我们只对形如6 N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。
以下代码需要自然数大于10 。
public int[] getPrimes(int n){
int []a = new int[200];
int k=0;
int num = 5;
a[0]=1;a[1]=2;a[2]=3;a[3]=5;a[4]=7;
for(int i=3;i< p>
for(int j=0;j<2;j++){
k = 2*(i+j)-1;
if((k<n)&&k%5==0?false:k%7==0?false:true){< p>
a[num] = k;
num++;
}
}
}
return a;
}
8. java语言：请输入一个整数，并判断他是否为素数 急！！ 正在考试
1. 根据概念判断:
如果一个正整数只有两个因子, 1和p，则称p为素数.
public boolean isPrime(int n)
{
if(n < 2) return false;
for(int i = 2; i < n; ++i)
if(n%i == 0) return false;
return true;
}
时间复杂度O(n).
2. 改进, 去掉偶数的判断
public boolean isPrime(int n)
{
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i < n; i += 2)
if(n%i == 0) return false;
return true;
}
时间复杂度O(n/2), 速度提高一倍.
3. 进一步减少判断的范围
定理: 如果n不是素数, 则n有满足1< d<=sqrt(n)的一个因子d.
证明: 如果n不是素数, 则由定义n有一个因子d满足1< d< n.
如果d大于sqrt(n), 则n/d是满足1< n/d<=sqrt(n)的一个因子.
public boolean isPrime(int n)
{
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i*i <= n; i += 2)
if(n%i == 0) return false;
return true;
}
时间复杂度O(Math.sqrt(n)/2), 速度提高O((n-Math.sqrt(n))/2).
4. 剔除因子中的重复判断.
定理: 如果n不是素数, 则n有满足1< d<=Math.sqrt(n)的一个"素数"因子d.
证明: I1. 如果n不是素数, 则n有满足1< d<=Math.sqrt(n)的一个因子d.
I2. 如果d是素数, 则定理得证, 算法终止.
I3. 令n=d, 并转到步骤I1.
由于不可能无限分解n的因子, 因此上述证明的算法最终会停止.
// primes是递增的素数序列: 2, 3, 5, 7, ...
// 更准确地说primes序列包含1->Math.sqrt(n)范围内的所有素数
public boolean isPrime(int primes[], int n)
{
if(n < 2) return false;
for(int i = 0; primes[i]*primes[i] <= n; ++i)
if(n%primes[i] == 0) return false;
return true;
}
5. 构造素数序列primes: 2, 3, 5, 7, ...
由4的算法我们知道, 在素数序列已经被构造的情况下, 判断n是否为素数效率很高;
下面程序可以输出素数表.
public class ShowPrimeNumber{
public static int[] getPrimeNums(int maxNum){
int[] primeNums = new int[maxNum/2+1];
int sqrtRoot;
int cursor = 0;
boolean isPrime;
for(int i=2;i<=maxNum;i++){
sqrtRoot = (int)Math.sqrt(i); //取平方根
isPrime = true;
for(int j=0;j< cursor;j++){
if(primeNums[j]>sqrtRoot)
break;
if(i%primeNums[j]==0){
isPrime = false;
break;
}
}
if(isPrime){
primeNums[cursor++] = i;
}
}
int[] result = new int[cursor];
System.array(primeNums,0,result,0,cursor);
return result;
}
public static void main(String[] args) throws Exception{
int maxNum = Integer.parseInt(args[0]);
int[] primeNums = getPrimeNums(maxNum);
System.out.println("共"+primeNums.length+"个素数");
for(int i=0;i< primeNums.length;i++){
System.out.print(primeNums[i]+",\t");
}
}
}
6.(在素数表中)二分查找
Arrays.BinarySearch方法:
该方法用于在指定数组中查找给定的值，采用二分法实现，所以要求传入的数组已经是排序了的。
该方法的基本语法格式为：
Static int binarySearch(byte[] a, byte key)
该方法返回数据中key元素所在的位置，如果没有key元素，则返回key应插入的位置：-（insertion point-1），如数组中的第一个元素就大于key，返回-1。
注：数组的数据类型可以是int[] byte[] short[] float[] long[] double[] char[] Object[]类型。
9. 怎样判断一个数是否为素数(在C语言或JAVA里)
关于素数的判定
所谓“筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”。他是古希腊的着名数学家。他采取的方法是，在一张纸上写上1到100全部整数，然后逐个判断它们是否是素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。
具体做法如下：
<1> 先将1挖掉(因为1不是素数)。
<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
<3> 用3去除它后面的各数，把3的倍数挖掉。
<4> 分别用4、5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如找1～50的素数，要一直进行到除数为47为止（事实上，可以简化，如果需要找1～n范围内素数表，只需进行到除数为n^2(根号n)，取其整数即可。例如对1～50，只需进行到将50^2作为除数即可。）
如上算法可表示为：
<1> 挖去1;
<2> 用刚才被挖去的数的下一个数p去除p后面各数，把p的倍数挖掉;
<3> 检查p是否小于n^2的整数部分（如果n=1000, 则检查p<31?），如果是，则返回(2)继续执行，否则就结束;
<4> 纸上剩下的数就是素数。
#include <stdio.h>
#include <math.h>
int main(void)
{
int i;
int j;
int a[101]; // 为直观表示，各元素与下标对应，0号元素不用
for (i = 1; i <= 100; i++) // 数组各元素赋值
a[i] = i;
for (i = 2; i < sqrt(100); i++) // 外循环使i作为除数
for (j = i + 1; j <= 100; j++) // 内循环检测除数i之后的数是否为i的倍数
{
if (a[i] != 0 && a[j] != 0) // 排除0值元素
if (a[j] % a[i] == 0)
a[j] = 0; // i后数若为i的倍数，刚将其置0(挖去)
}
int n = 0; // 对输出素数计数, 以控制换行显示
for (i = 2; i <= 100; i++) // 输出素数
{
if (a[i] != 0)
{
printf("%-5d", a[i]); // 输出数组中非0元素(未挖去的数)
n++;
}
if (n == 10)
{
printf("\n"); // 每行10个输出
n = 0;
}
}
printf("\n");
return 0;
}
运行结果(VC):
=================================================
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97
=================================================
10. 写出求最大支撑树的算法，既此支撑树有可能的最大开销。
Prime算法或kruskal算法