Что не так с логикой?

Question

Я пытаюсь написать простой генератор, который реализует сито Эратосфена. Тем не менее, он включает в себя некоторые составные числа (например, 25, 49 и другие кратные 5 и 7) в выводе.

Вот мой код:

/*****
 * To find out prime numbers from 1 to 100 with a different procedure
 * Author:Udit Gupta
 * Date:20/08/2011
 */

#include<stdio.h>

int main() {
    int a[100],i,j,k,n;

    for(i=0;i<=99;i++)
        a[i] = i+1;  /*1 to 100 numbers are entered into array*/

    /*Here te actual logic starts .......*/
    j = 1;
    while ( (a[j] != 0) && (j!=50) ) {
        k = 1;
        n = a[j];

        while( (n * k) < 99) {
            a[j+(n*k)] = 0;
            k++;
        }

        j++;
    }

    /*To print output of the array*/
    for (i=0;i<=99;i++) {
        if ( a[i] != 0)
            printf("\n%d",a[i]);
    }

    return 0;
}

Вот вывод ....

    
udit@udit-Dabba ~/Desktop/letusc/ch8 $ gcc -o Dd Dd.c -Wall
udit@udit-Dabba ~/Desktop/letusc/ch8 $ ./Dd

1 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97

Answer 1

Честно говоря, сделайте себе одолжение и сделайте поиск в Интернете по "учебнику по отладчику gdb".Вы получите сотни хитов.Затем сядьте и повеселитесь, изучая мощный инструмент, который вы потратите на сотни и сотни часов, если продолжите изучать C, C ++ или дюжину других компьютерных языков.(Я серьезно отношусь к «веселой» части; если вы не находите это забавным, бросьте CS!)

Также выполните поиск по «ddd debugger»;это бесплатный графический интерфейс OSS для GDB - очень хорошо, ИМХО.

-k

Answer 2

while (n * k < 99) {
  a[j + n * k] = 0;
  k++;
}

Этот код опасен.Возможно, в конечном итоге j + n * k будет больше 99, что приведет к перезаписи произвольной памяти (или, строго говоря, поведение не определено ).Лучше быть в безопасности:

#include <assert.h>

...

while (n * k < 99) {
  int index = j + n * k;
  assert(0 <= index && index < 100);
  a[index] = 0;
  k++;
}

Answer 3

1-я подсказка: в отладчике разрыв строки n = a[j];.Запустите несколько итераций.Останавливается ли оно когда a[j] == 5?

udit@udit-Dabba ~/Desktop/letusc/ch8 $ gdb ./Dd
[GDB preamble elided]
(gdb) b main
Breakpoint 1 at 0x100000e63: file Dd.c, line 12.
(gdb) r
Starting program: /home/udit/Desktop/letusc/ch8/Dd
Reading symbols for shared libraries +. done

Breakpoint 1, main () at Dd.c:12
12      for(i=0;i<=99;i++)
(gdb) watch n
Hardware watchpoint 2: n
(gdb) c
Continuing.
Hardware watchpoint 2: n

Old value = 0
New value = 2
main () at Dd.c:21
21          while( (n * k) < 99) {
(gdb) c
Continuing.
Hardware watchpoint 2: n

Old value = 2
New value = 3
main () at Dd.c:21
21          while( (n * k) < 99) {
(gdb) p j
$1 = 2
(gdb) 

RMS (не имеет отношения к , что RMS ) Учебное пособие по GDB включает раздел о контрольных точках , который используется в приведенном выше примере сеанса.

Дополнительные подсказки, которые вам понадобятся.

Answer 4

Проблема в том, что цикл заканчивается слишком рано. если a == 3, a[j] == 0 и цикл заканчивается. Измените ваш основной цикл на:

for (j = 1; j < 50; j++) 
{
    k = 1;
    n = a[j];

    if (n != 0) 
        while (j + n * k <= 99) 
        {
            a[j + n * k] = 0;
            k++;
        }
}

Answer 5

Вы сохраняете свои результаты (помечая не простые числа как ноль) в том же массиве, который вы читаете из внешнего цикла.

Число 4 помечается (правильно) как не простое, ноэто имеет нежелательный побочный эффект завершения вашего основного цикла (потому что a [j] == 0).

Таким образом, вы обрабатываете только n = 2 и n = 3.

Answer 6

подсказка;посмотрите на то, что случилось с 5 и, следовательно, 25

Google скажет вам, как использовать GDB - это не сложно

a[j + n * k] = 0;

Я думаю, вы имеете в виду

a[n * k] = 0;