用ArrayList和LinkedList求素数，并对比两种集合类的耗时

妖狐艹你老母 2022-11-08 14:17 10阅读 0赞

### 用ArrayList和LinkedList求素数，并对比两种集合类的耗时 ###

*  用ArrayList和LinkedList求小于某个正整数的所有素数，并比较耗时
 *   *  设计思路
 *  ArrayList集合类
 *   *  代码
     *  运行截图
 *  LinkedList集合类
 *   *  代码
     *  运行截图
 *  耗时对比
 *   *  两者区别

# 用ArrayList和LinkedList求小于某个正整数的所有素数，并比较耗时 #

## 设计思路 ##

解决这个题目可以使用双重循环来完成，外层用于确定数的范围，内层用于判断当前数是否为素数。  
不管是**ArrayList**集合类还是**LinkedList**集合类，都可以用以下思路设计代码：

> 先创建两个列表，一个用来保存待查数字的列表，另一个用来保存已经确认的素数列表，两个列表均为空。  
> 之后将待查列表的第一个数放进素数列表，这个数字为2,。然后将待查列表中所有该数的整数倍数字全部删除；重复完成上述操作，直至待查列表为空。

# ArrayList集合类 #

## 代码 ##

import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Example_06_2 {
        
        public static void main(String[] args) {
        
            Scanner scanner =new Scanner(System.in);
            System.out.println("please input a number:");
            int mixNumber2 =scanner.nextInt();//输入给定范围正整数
            ArrayList<Integer> numbers2=new ArrayList<Integer>();//定义待查列表
            ArrayList<Integer> prim2=new ArrayList<Integer>();//定义素数列表
            for (int i = 2; i < mixNumber2; i++) {
        //给数组赋值
                numbers2.add(i);
            }
            long startTime = System.currentTimeMillis();//计算程序起始时间
    
            int first;
            while (numbers2.size()>0){
        
                first=numbers2.remove(0);//把待查列表第一个元素赋值给first
                prim2.add(first);//将first添加到素数列表
                for (int i = 2; i < numbers2.size(); i++) {
        
                    if (i % first==0){
        //如果第i个元素能把第一个元素整除，则移除第i个元素
                        numbers2.remove(i);
                    }
    
                }
            }
            long endTime =System.currentTimeMillis();//计算程序结束时间
            System.out.println(numbers2);
            System.out.println("---------以上是待查列表--------");
            System.out.println(prim2);
            System.out.println("素数数组长度："+prim2.size());
            System.out.println("程序执行所需时间："+(endTime-startTime)+"毫秒");
        }
    
    }

## 运行截图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwMjE4NjM2_size_16_color_FFFFFF_t_70_pic_center]

# LinkedList集合类 #

## 代码 ##

import java.util.LinkedList;
    import java.util.Scanner;
    
    public abstract  class Example_06 {
        
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            System.out.println("please input a number:");
            int mixNumber =scanner.nextInt();//输入给定范围正整数
            LinkedList<Integer> numbers=new LinkedList<Integer>();//创建待查列表
            LinkedList<Integer> prim=new LinkedList<Integer>();//创建素数列表
            for (int i = 2; i < mixNumber; i++) {
        //给列表赋值
                numbers.add(i);
            }
            long startTime = System.currentTimeMillis();//计算程序起始时间
            int first=0;
            while (numbers.size()>0){
        
                first=numbers.removeFirst();//把待查列表第一个元素赋值给first
                prim.add(first);//将first添加到素数列表
                for (int i = 0; i < numbers.size(); ) {
        
                    int num =numbers.get(i);
                    if (num %first ==0){
        //如果第i个元素能把第一个元素整除，则移除第i个元素
                        numbers.remove(i);
                    }
                    else {
        
                        i++;
                    }
    
                }
            }
           long endTime =System.currentTimeMillis();//计算程序结束时间
            System.out.println(numbers);
            System.out.println("---------以上是待查列表--------");
            System.out.println(prim);
            System.out.println("素数数组长度："+prim.size());
            System.out.println("程序执行所需时间："+(endTime-startTime)+"毫秒");
        }
    }

## 运行截图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwMjE4NjM2_size_16_color_FFFFFF_t_70_pic_center 1]

# 耗时对比 #

在两个运行截图中我们可以看到，我输入了**10000**，让这两个代码在**10000个正整数**中找出所有素数，ArrayList集合类的代码所耗时只需**53毫秒**，而LinkedList集合类的代码耗时需要**639毫秒**。所以结果显而易见。

## 两者区别 ##

ArrayList集合类分配的空间大于实际存储的数据个数，这样便于添加和插入元素，但是插入、删除元素需要进行数据移动等内存操作，所以查询、索引等操作速度快，而插入、删除等操作速度慢；LinkedList集合类是另外一个常用的线性列表集合。但是其内部结构和ArrayList完全不同，它采用的是双链表结构，这使得在插入、删除操作时非常快捷方便。但由于在完成遍历查询是无法保存上一次的查询位置这使得实现查询操作效率低下。

本篇文章到这就结束了，觉得写得还可以的话点个一键三连吧。  
由于本人实力有限，如果写得不清楚的欢迎评论区交流；有可以优化的地方欢迎大佬指教指教。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwMjE4NjM2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/846c6fe87b4e4129b47b3161667b7287.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwMjE4NjM2_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221023/65291221378d4e039846bf48f6ff4bcd.png