Циклы и простые номера

Question

Напишите программу, которая запрашивает у пользователя целое число и затем распечатывает все простые числа до этого целого числа. Например, когда пользователь вводит 20, программа должна печатать 2 3 5 7 11 13 17 19 Вспомните, что число является простым числом, если оно не делится на любое число, кроме 1 и самого.

Я пытаюсь написать эту программу, но у меня возникают трудности, может ли кто-нибудь показать мне, как написать этот код? Это то, что я написал, но это совершенно неправильно.

import java.util.Scanner; 

public class PrimeNumbers 
{ 
    public static void main(String[] args) 
    { 
     Scanner in = new Scanner(System.in); 

     System.out.print("Enter Integers: "); 
     int x; 
     int n = in.nextInt(); 

     for (int i = 2; i < n ; i++) 
     { 
      x = i; 

      if (n % i != 0 && i % x != 0) 
      { 
       System.out.println(i); 
      } 
      x--; 
     } 
    } 
} 

Answer 1

Вычисляет число простых чисел, меньших или равных N, используя решета Эратосфена.

% Java PrimeSieve 25 количество простых чисел < = 25: 9

% Java PrimeSieve 100 количество простых чисел < = 100 25

% Java -Xmx100m PrimeSieve 100000000 Количество простые числа < = 100000000 является 5761455

% Java PrimeSieve -Xmx1100m 1000000000 число простых чисел < = 1000000000 является 50847534

110MB и 1100MB - это объем памяти, который вы хотите выделить программе . Если ваш компьютер имеет меньше, чтобы это число меньше, но это может помешать вам от решения проблемы для очень больших значений N.

class PrimeSieve { 
    public static void main(String[] args) { 
     int N = Integer.parseInt(args[0]); 

     // initially assume all integers are prime 
     boolean[] isPrime = new boolean[N + 1]; 
     for (int i = 2; i <= N; i++) { 
      isPrime[i] = true; 
     } 

     // mark non-primes <= N using Sieve of Eratosthenes 
     for (int i = 2; i*i <= N; i++) { 

      // if i is prime, then mark multiples of i as nonprime 
      // suffices to consider mutiples i, i+1, ..., N/i 
      if (isPrime[i]) { 
       for (int j = i; i*j <= N; j++) { 
        isPrime[i*j] = false; 
       } 
      } 
     } 

     // count primes 
     int primes = 0; 
     for (int i = 2; i <= N; i++) { 
      if (isPrime[i]){ primes++; System.out.print(i+", ");} 
     } 
     System.out.println("\nThe number of primes <= " + N + " is " + primes); 
    } 
} 

Answer 2

Используйте этот метод, чтобы проверить, является ли данное int простым.

public static boolean isPrime(int a) 
{ 
    if (a == 2) 
     return true; 
    int midpoint = Math.round(a/2); 
    for(int i = 2; i < midpoint; i++) 
    { 
     if(a % i == 0) 
      return false; 
    } 
    return true; 
} 

Объяснение: Перебор всех чисел вплоть до середины и модуля, пока не сталкиваются с 0 или нет. Если вы столкнулись с 0, верните значение false, потому что мы знаем, что оно не является простым, если мы не встретим нуля, мы вернем true, потому что оно является простым.
Мы зацикливаемся до середины, потому что нет необходимости зацикливаться дальше.

Вы можете реализовать его в петле через

for (int i = 2; i < n ; i++) 
{ 
    if (isPrime(i)) 
    { 
     System.out.println(i); 
    } 
}