Сканирование 2d массива для простых чисел в C - PullRequest
Новая
       9

Сканирование 2d массива для простых чисел в C

0 голосов
/ 29 ноября 2018

У меня есть массив 20x20, сгенерированный случайным образом.Мне нужна функция для сканирования массива, поиска всех простых чисел в массиве и добавления их в новый массив.Массив был сгенерирован так: 

#define TOTAL_ROWS 20
#define TOTAL_COLUMNS 20

void fillMatrix(int A[TOTAL_ROWS][TOTAL_COLUMNS], int *set_rows, int *set_columns)
{
    int rows = 20, columns = 20;
    for(int i = 0; i < rows; i++)
        for(int j = 0; j < columns; j++)
            A[i][j] = rand() % 500;

    *set_rows = rows;
    *set_columns = columns;
}

У меня также есть сортировка, с помощью этой функции: 

void sortMatrix(int A[TOTAL_ROWS][TOTAL_COLUMNS], int rowsize, int colsize)
{
    for(int r = 0; r < rowsize; r++)
        qsort(A[r], colsize, sizeof(int), compare);
}

Также есть функция отображения.Вот main, который вызывает функции: 

int main(void)
{
    int array[TOTAL_ROWS][TOTAL_COLUMNS] = { 0 };
    int rows, columns;
    fillMatrix(array, &rows, &columns);
    sortMatrix(array, rows, columns);
    displayArray(array, rows, columns);
    return  0;
}

Пример сгенерированного массива: 

  0  41 145 169 205 224 281 327 327 334 358 436 442 461 462 464 467 478 491 495 
 35  38 104 153 167 216 218 226 271 292 299 369 382 391 394 395 402 412 421 447 
 29  37  47 141 144 162 164 173 203 211 223 241 253 257 278 311 322 333 359 368 
  6  35  40  48 101 106 148 190 229 264 288 305 316 342 350 370 390 393 442 446 
 37  38  41  82  84 118 123 126 129 256 308 323 340 376 429 431 439 444 454 466 
 12  21  72  73  97 115 139 158 173 204 245 270 277 306 329 333 386 424 430 477 
  7  31  52  74 107 136 150 155 161 191 224 267 290 337 350 355 430 441 466 486 
  6  30  88  91 155 168 209 221 253 258 262 287 383 400 409 413 422 445 446 457 
 20  21  37  41  48  95  96 102 124 168 199 291 336 348 350 359 374 410 483 484 
 14  53 117 127 148 228 234 281 288 307 310 313 393 400 418 421 438 467 483 499 
  8  19  56  93 100 109 116 195 202 224 249 298 303 309 343 344 435 451 485 489 
  3   9  23  38  80  87  89 118 122 157 200 281 292 296 298 298 314 448 458 472 
 11  38  55 134 146 156 157 179 190 191 202 272 315 328 362 375 386 388 433 458 
  3  10  21  57  75 100 142 151 199 212 322 344 369 369 381 389 392 416 476 498 
  2  85  88 117 154 169 182 188 189 221 255 257 285 289 332 361 401 423 426 432 
 12  29  49  55  60 139 145 187 192 218 253 279 329 368 423 425 434 441 476 496 
 49 105 114 171 193 195 201 234 263 282 286 286 297 316 366 416 437 449 455 488 
 53  58 129 144 146 161 185 196 222 256 308 313 313 321 332 355 412 445 481 482 
 10  18  22  24  35  44 149 154 159 168 173 186 245 253 292 313 439 450 466 474 
 18  70 125 159 177 202 287 297 314 324 333 334 372 374 391 405 414 458 477 487

Мне нужна функция isPrime () для перехода в main, которая найдет каждое простое число вмассивы и добавить их в новый массив.Я просто не знаю как.

Ответы [ 2 ]

0 голосов
/ 29 ноября 2018

Самый быстрый способ - запустить сито Эратосфена: 

bool prime[max_number + 1];
void sieve() 
{  
    memset(prime, true, sizeof(prime)); 

    for (int i=2; i*i<=max_number; i++) 
    { 
        if (prime[i] == true) 
        { 
            for (int j=i*i; j<=max_number; j += i) 
                prime[j] = false; 
        } 
    } 
}

и использовать массив prime для поиска, чтобы проверить, является ли данное число p простым в постоянном времени, просто проверивесли prime[p] == true.Здесь max_number должно быть максимальное число, которое вы будете иметь в качестве входа.

0 голосов
/ 29 ноября 2018

Вы можете использовать это. 

int is_prime(int num)
{
     if (num <= 1) return 0;
     if (num % 2 == 0 && num > 2) return 0;
     for(int i = 3; i < num / 2; i+= 2)
     {
         if (num % i == 0)
             return 0;
     }  
     return 1;
}
int prime_numbers_array[10000];
int array_length = 0;
int i,j;
for(i = 0; i < rows; i++){
    for(j = 0 ;j < cols; j++){
         if(is_prime(array[i][j])){
              prime_numbers_array[array_length++] = array[i][j]
          }
     }
  }
...