Программа для поиска выполнения простых чисел занимает некоторое время

Question

Я написал программу C для печати простого числа на заданном диапазоне для упражнений. Это код:

#include <stdio.h> 
#include <stdbool.h> 

int main (void) { 
int num1,int num2; 
bool flag; 
int i,j,count=0; 

printf("Enter range 1:");scanf("%d",&num1); 
printf("Enter range 2:");scanf("%d",&num2); 

if(num1<2) 
    num1++; 

for(i=num1;i<=num2;i++){ 
    j=2; 
    while(j<i){ 
     if(i%j==0){ 
      flag=false; 
      break; 
     } 
     else{ 
      flag=true; 
     } 
     j++; 
    } 
    if(flag){ 
     printf("%d ",i); 
     count++; 
    } 
} 
printf("\n"); 
printf("Number of prime number between %d and %d is %d\n", 
              num1,num2,count); 
return 0; 
} 

код работает, как я ожидал, но когда я входной диапазон между 1-100000 или больше программой печатью вывода, как бесконечное зацикливание, и я должен подождать некоторое время для программы печати все простое число.

Мой вопрос в том, почему программа занимает некоторое время, чтобы распечатать все простые числа между диапазоном 1-100000 или больше?

Answer 1

Некоторые незначительные улучшения:

• Пропустить все четные числа, кроме 2.
• Условие j<i не требуется, вычисление до тех пор, пока квадратный корень i не будет достаточным.

Однако для больших чисел он по-прежнему не быстрый, поскольку алгоритм работает медленно. Рассмотрим эффективный алгоритм для нахождения простых чисел, например: Sieve of Eratosthenes.

Answer 2

почему программа занять некоторое время

1. Поскольку все программы потребуется некоторое время (и это время, как правило, зависит от эффективности алгоритмов, используемых программой).
2. Вы использовали очень неэффективный алгоритм, чтобы решить, является ли число простым
3. Вы должны изучить вычислительную сложность (обозначения большой-O), и посмотреть, сколько операций ваша программа выполняет (а много).

Answer 3

Приведенный ниже код даст вам лучшую эффективность. В вашем коде много ненужных проверок.

for(i=num1;i<=num2;i++) 
    { 
     flag = 0; 
     for(j=2;j<=(i/2);j++) 
     { 
     if(i%j == 0) 
     { 
      flag = 1; 
      break; 
     } 
     } 
     if(!flag) 
     { 
     printf("%d ",i); 
     count++; 
     } 
    }