Не удается реализовать Решето Эратосфена

@Лера789 · Регистрация: 02.11.2012

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

задача: быстро найти простые числа. проблема в том, что в СИ разбираюсь плохо ( так что код может кому-то показаться наивным ). прошу найти ошибки в алгоритме

C

  
   #include<stdio.h>
   #include<stdlib.h>
   #include<conio.h>
   #include<time.h>
 
 
  int main()
   {
      int L=2, N=30, A[305], j, x=0; 
      clock_t start,end;
      
      start=clock();
// заполнение массива нулями       
       for ( L; L<=N; L++)  
      {         
        A[L]=0;
        printf("%d\n",A[L]);   
      }
      L=2;
// алгоритм решето Эратосфена
       for ( L, x; j<=N; L++, x++)
       {
           if (A[L])
           j=L*L+L*x;    
           A[j]=0;
       }    
       L=2;
//вывод новых значений        
       for ( L; L<=N; L++)          
        printf("%d\n",A[L]);
        
        end=clock();
        printf(" %6.3f sec\n",(double)(end-start)/(double)CLOCKS_PER_SEC);
      getch();
      return 0;
   }

@UriahHeep · 04.11.2013, 21:14

Лера789, в 23-й строке вы используете неопределённую переменную j, на момент первого прохождения по циклу for в j может быть всё что угодно.

Добавлено через 5 минут
А здесь вы что имели ввиду?

C

if (A[L])
j=L*L+L*x;    
A[j]=0;

Только вторая строка должны быть в теле условия или вторая и третья?

Мой совет: ВСЕГДА выделяйте тело условия фигурными скобками, даже если блок состоит из одного оператора.

C

if (A[L]) {
    j=L*L+L*x;
}
A[j]=0;

C

if (A[L]) {
    j=L*L+L*x;
    A[j]=0;
}

@Лера789 · 04.11.2013, 23:46 **[ТС]**

C

   #include<stdio.h>
   #include<stdlib.h>
   #include<conio.h>
   #include<time.h>
 
 
  int main()
   {
      int L=2, N=30, A[305], j=0, x=0; 
      clock_t start,end;
      
      start=clock();
// çàïîëíåíèå ìàññèâà íóëÿìè       
       for ( L; L<=N; L++)          
        A[L]=1;  
      L=2;
// àëãîðèòì ðåøåòî Ýðàòîñôåíà
       for ( L, x; j<=N; L++, x++)
       {
           if (A[L])
           j=L*L+L*x;    
           A[j]=0;
       }    
       L=2;
//âûâîä íîâûõ çíà÷åíèé        
       for ( L; L<=N; L++)          
       { 
           if (A[L])
             printf("%d\n",L);
       }  
        end=clock();
        printf(" %6.3f á¥ª\n",(double)(end-start)/(double)CLOCKS_PER_SEC);
      getch();
      return 0;
   }

исправила логические ошибки. но все равно находит не то

про скобки возьму на заметку )

Добавлено через 2 часа 26 минут
код работает но с дефектом
по условию надо Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent"

C

// ïîïûòêà ðåàëèçîâàòü ðåøåòî Ýðàòîñôåíà   
  
   #include<stdio.h>
   #include<stdlib.h>
   #include<conio.h>
   #include<time.h>
 
 
  int main()
   {
      int L=5, N=10, A[30], j=0; 
      clock_t start,end;
      
      start=clock();
// çàïîëíåíèå ìàññèâà åäèíèöàìè     
       for ( L; L<=N; L++)          
        A[L]=1;  
      L=5;
// àëãîðèòì ðåøåòî Ýðàòîñôåíà
       for ( L; L*L<=N; L++)
           {  
                if (A[L]) 
                {
                   for (j=L*2; j<=N ;j=j+L)
                  {  A[j]=0; 
                  } 
                }
           }  
       
       L=5;
//âûâîä íîâûõ çíà÷åíèé    
         
       for ( L; L<=N; L++)          
       { 
           if (A[L])    printf("%d\n",L);  
           printf("Absent\n");  
       }  
        end=clock();
        printf(" %6.3f á¥ª\n",(double)(end-start)/(double)CLOCKS_PER_SEC);
      getch();
      return 0;
   }

@UriahHeep · 05.11.2013, 11:59

Сначала у вас N=30, A[305] (видимо, 305 -- это опечатка), а теперь N=10, A[30], т.е. вы имеете массив из 30-ти элементов, а в циклах проходите по 10-ти элементам.

Зачем вам массив из единиц? Вы собрались искать простые числа в массиве из единиц?

C

// заполнение массива единицами     
       for ( L; L<=N; L++)          
        A[L]=1;  
      L=5;

и то здесь только первые N=10 элементов из 30-ти равны единицам, остальные случайные числа из памяти.

И почему теперь у вас L=5?

P.S. Осталось ещё немного подумать и у вас всё получится, надеюсь.

@UriahHeep 224 / 219 / 77 Регистрация: 24.09.2012 Сообщений: 511 Записей в блоге: 2
	04.11.2013, 21:14	2
	Лера789, в 23-й строке вы используете неопределённую переменную j, на момент первого прохождения по циклу for в j может быть всё что угодно. Добавлено через 5 минут А здесь вы что имели ввиду? C if (A[L]) j=LL+Lx; A[j]=0; Только вторая строка должны быть в теле условия или вторая и третья? Мой совет: ВСЕГДА выделяйте тело условия фигурными скобками, даже если блок состоит из одного оператора. C if (A[L]) { j=LL+Lx; } A[j]=0; C if (A[L]) { j=LL+Lx; A[j]=0; } 0

@UriahHeep 224 / 219 / 77 Регистрация: 24.09.2012 Сообщений: 511 Записей в блоге: 2
	05.11.2013, 11:59	4
	Сначала у вас N=30, A[305] (видимо, 305 -- это опечатка), а теперь N=10, A[30], т.е. вы имеете массив из 30-ти элементов, а в циклах проходите по 10-ти элементам. Зачем вам массив из единиц? Вы собрались искать простые числа в массиве из единиц? C // заполнение массива единицами for ( L; L<=N; L++) A[L]=1; L=5; и то здесь только первые N=10 элементов из 30-ти равны единицам, остальные случайные числа из памяти. И почему теперь у вас L=5? P.S. Осталось ещё немного подумать и у вас всё получится, надеюсь. 0