C Language Programming: Prime Number Detection Using Trial Division and Simple Application of Backtracking (Eight Queens Problem)

Prime Number Detection Using Trial Division

A prime number, also known as a prime, is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers, meaning it is only divisible by 1 and itself.

Here is a trial division (enumeration) algorithm to filter out the prime numbers that meet the criteria for reference:

void fun(int m,int k,int xx[])
{
    int i = m, ch = 0, jxbj;
    do{
        i++;
        for (jxbj=2;jxbj<i;){
            if (i % jxbj == 0){
                break;
            }else{
                jxbj++;
                if (jxbj == i - 1){
                    xx[ch++] = i;
                }
            }
        }
    }while(ch<k);
}

void main()
{
   int m, n, zz[1000];
   printf( "\nPlease enter two integers:");
   scanf("%d%d", &m, &n);
   fun(m, n, zz);
   for(m = 0; m < n; m++)
      printf("%d ", zz[m]);
   printf("\n");
}

Simple Application of Backtracking (Eight Queens Problem)

The author compiled this under Dev-C++ 5.11.

The problem is:

Place 8 queens on an 8×8 chessboard such that no two queens threaten each other, meaning they are not in the same row, column, or diagonal. Output all distinct arrangements, with each arrangement displayed on an 8×8 board, using “Q” to represent a queen and “*” to represent an empty space. Separate each row of the board with a blank line, and output the arrangements in lexicographical order. No input is required for this problem.

#include <stdio.h>
#include <stdlib.h> //Also we can use <math.h>
//  This program aims to solve the eight-queens problem.
//  edited by yyh   22/8/2025   23:43
int a[8][8];
int col[8];
int sum = 0;
int main(void){
    int i, j;
    for (i = 0; i < 8; i++)
        for (j = 0; j < 8; j++)
            a[i][j] = 0;
    ba_huang_hou(0);
    printf ("The final result is %d", sum);
}

void ba_huang_hou(int row){
    int c;
    if (row == 8){
        sum++;
        print_chess();
        return;
    }
    
    for(c = 0; c < 8; c++){ 
        col[row] = c;
        if(check(row)){
            a[row][c] = 1;
            ba_huang_hou(row + 1);
            a[row][c] = 0;
        }
    }
}

int check(int row){
    int i;
    for(i = 0; i < row; i++){
        if (col[i] == col[row] || abs(row - i) == abs(col[row] - col[i])){
            return 0;
        } 
    }
    return 1;
}

void print_chess(){
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j)
            printf("%c ", a[i][j] ? 'Q' : '*');
        putchar('\n');
    }
    printf("----------\n");
}

Example Output: