Простые числа

@sanchopa · Регистрация: 21.04.2010

Author24 — интернет-сервис помощи студентам

Программа делает следующее: берет текстовый файл в котором хранятся порядковые номера простых чисел, находит максимальный порядковый номер, и потом в аррейлист записывает все простые числа до числа с тем максимальным порядковым номером из файла. Вообще все сводится к проверки чисел на простоту! Как это быстрее сделать? у меня сейчас проверяется делится ли нацело число на ПРОСТЫЕ перед ним, кроме как на само себя. Еще есть такое свойство "число простое, если оно не делится нацело ни на одно из ПРОСТЫХ чисел меньше квадратного корня из самого себя"
и когда я ставлю это условие(меньше квадратного корня из самого себя) то почему то срабатывает не правильно

Java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws FileNotFoundException {
 
        ArrayList<Integer> list = new ArrayList<Integer>();// создаем арейлист
 
        // читаем из файла в лист т.к. не знаем размеров
        Scanner in = new Scanner(new File("числа.txt"));
        while (in.hasNext()) {
            list.add(in.nextInt());
        }
        
        int MAX = 0;//зануляем максимальный порядковый номер
        //находим и запоминаем макс.поряд.номер
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > MAX) {
                MAX = list.get(i);
            }
        }
 
        
        ArrayList<Integer> list2 = new ArrayList<Integer>();//аррей лист для простых чисел
        list2.add(2);//записываем первое простое число
        int i = 1;//любое число с 1 т.к. первое ч. уже записано
        int x = 3;//т.к. первое п.ч. записано начинаем с второго
 
        while (MAX != i) {//делаем пока i не равно максимальному числу
            boolean flag = true;
            for (int j = 0; j < list2.size(); j++) {
                if(list2.get(j) < Math.sqrt(x)){
                if (x % list2.get(j) == 0)// если остаток от деления
                // последнего найденого простого
                // числа = 0, то это не простое
                // число
                { 
                    flag = false;
                }
                }
            }
            
            if (flag) {
                i++;
                list2.add(x);
 
            }
            x++;
            
        }
 
        for (int k = 0; k < list.size(); k++) {
            System.out.println(list2.get((list.get(k))-1));
        }
    }
}

а вот без него все впорядке

Java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws FileNotFoundException {
 
        ArrayList<Integer> list = new ArrayList<Integer>();// создаем арейлист
 
        // читаем из файла в лист т.к. не знаем размеров
        Scanner in = new Scanner(new File("числа.txt"));
        while (in.hasNext()) {
            list.add(in.nextInt());
        }
        
        int MAX = 0;//зануляем максимальный порядковый номер
        //находим и запоминаем макс.поряд.номер
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > MAX) {
                MAX = list.get(i);
            }
        }       
        ArrayList<Integer> list2 = new ArrayList<Integer>();//аррей лист для простых чисел
        list2.add(2);//записываем первое простое число
        int i = 1;//любое число с 1 т.к. первое ч. уже записано
        int x = 3;//т.к. первое п.ч. записано начинаем с второго
 
        while (MAX != i) {//делаем пока i не равно максимальному числу
            boolean flag = true;
            for (int j = 0; j < list2.size(); j++) {
                if (x % list2.get(j) == 0)// если остаток от деления
                // последнего найденого простого
                // числа = 0, то это не простое
                // число
                {
                    flag = false;
                }
            }
                if (flag) {
                i++;
                list2.add(x);
 
            }
            x++;
            
            }
 
        for (int k = 0; k < list.size(); k++) {
            System.out.println(list2.get((list.get(k)-1)));
        }
    }
}

@RequiemMass · 22.01.2012, 18:42

Я исследовал твой алгоритм для MAX=10. Я не очень понимаю смысл задачи твоей, но если макс равно 10 то почему то при твоих счётчиках число до которого будет считать равно 30. Всё дело в том что у тебя MAX сравнивается почему то не с числом x, а с количеством простых чисел. Ну м.б так и надо. Так вот я внёс следующие улучшения, всё работает для MAX=10 правильно.

Java

   int MAX=10;
        ArrayList<Integer> list2 = new ArrayList<Integer>();//аррей лист для простых чисел
                list2.add(2);//записываем первое простое число
                int i = 1;//любое число с 1 т.к. первое ч. уже записано
                int x = 3;//т.к. первое п.ч. записано начинаем с второго
 
                while (MAX != i) {//делаем пока i не равно максимальному числу
                        boolean flag = true;
                        double sqrt = Math.sqrt(x);//Это чтобы лишний раз не считать
//для каждого x нового считаем всего лишь 1 раз
                        for (int j = 0; j < list2.size(); j++) {
                                
                                if(list2.get(j) <= sqrt ){//Тут важно ставить (<=)
//Иначе если у нас на входе число 4 и мы должны проверить его делимость на 2
//условие не сработает потому что 2 = 2 соответственно для этого теста где MAX=10
//можешь попробовать убрать это условие и посмотреть как работает алгоритм.
                                if (x % list2.get(j) == 0)
                                {
                                       flag = false;
                                       break;//Это чтобы лишний раз не считать если 
//делится ХОТЯ БЫ НА 1 ЧИСЛО то мы перестаём считать
                                }
                                }
                        }
                        
                        if (flag) {
                            i++;
                            list2.add(x);
                        }
                        x++;
                        
                }
                
                for (int k =0;k<list2.size();k++)
                {
                    System.out.println(list2.get(k));
                }
    }

@sanchopa · 22.01.2012, 19:51 **[ТС]**

Спасибо, разобрался, ниже код программы которая на входе в текстовом файле получает порядковые номера, а выводит ПРОСТЫЕ числа соответствующие поряд. номерам.
н-р
На входе текстовый файл:

1
3
2

На выходе:

2
5
3

(2-первое простое число, 5-третье простое число, 3-второе простое число)

Java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws FileNotFoundException {
 
        ArrayList<Integer> list = new ArrayList<Integer>();// создаем арейлист
 
        // читаем из файла в лист т.к. не знаем размеров
        Scanner in = new Scanner(new File("числа.txt"));
        while (in.hasNext()) {
            list.add(in.nextInt());
        }
 
        int MAX = 0;// зануляем максимальный порядковый номер
        // находим и запоминаем макс.поряд.номер
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > MAX) {
                MAX = list.get(i);
            }
        }
        ArrayList<Integer> list2 = new ArrayList<Integer>();// аррей лист для
                                                            // простых чисел
        list2.add(2);// записываем первое простое число
        int i = 1;// любое число с 1 т.к. первое ч. уже записано
        int x = 3;// т.к. первое п.ч. записано начинаем с второго
 
        while (MAX != i) {// делаем пока i не равно максимальному числу
            double sqrt = Math.sqrt(x);
            boolean flag = true;
            for (int j = 0; j < list2.size(); j++) {
                if (list2.get(j) <= sqrt) {// если простое число меньше корня из
                                            // числа которое проверяем
                    if (x % list2.get(j) == 0)// если остаток от деления
                    // последнего найденого простого
                    // числа = 0, то это не простое
                    // число
                    {
                        flag = false;
                        break;//если делится ХОТЯ БЫ НА 1 ЧИСЛО то мы перестаём считать
                    }
                }
            }
            if (flag) {
                i++;//переход на след. иттерацию
                list2.add(x);//добавление найденного п.ч.
            }
            x++;//след. число для проверки
        }
        //------------------ВЫВОД---------------------------------
        for (int k = 0; k < list.size(); k++) {
            System.out.println(list2.get((list.get(k)) - 1));
        }
    }
}

	22.01.2012, 19:51