Program to Find Prime Numbers

Find prime numbers from a given range of numbers parallel program

I don't have the OMP software installed, so I had to remove the parallelization. However, the code works once the 'print out the prime numbers' loop is adjusted to deal with the fact that the algorithm knows that 2 is the only even prime number and that it stores the primality of an odd number X in isPrime[X / 2].

This leads to this code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#include <omp.h>

static char isPrime[1000];

// odd-only sieve
//static int eratosthenesOdd(int N, int useOpenMP)
static int eratosthenesOdd(int N)
{
    /* enable/disable OpenMP */
    //omp_set_num_threads(useOpenMP ? omp_get_num_procs() : 1);

    /* instead of i*i <= N we write i <= sqr(N) to help OpenMP */
    const int NSqrt = (int)sqrt((double)N);
    int memorySize = (N - 1) / 2;

    int i, j;
    /* Let all numbers be prime initially */
    //#pragma omp parallel for
    for (i = 0; i <= memorySize; i++)
    {
        isPrime[i] = 1;
    }


    /* find all odd non-primes */
    //#pragma omp parallel for schedule(dynamic)
    for (i = 3; i <= NSqrt; i += 2)
    {
        if (isPrime[i / 2])
        {
            for (j = i * i; j <= N; j += 2 * i)
            {
                isPrime[j / 2] = 0;
            }
        }
    }


    printf("2\n");
    for (int k = 3; k <= N; k += 2)
    {
        if (isPrime[k / 2] == 1)
        {
            printf("%d\n", k);
        }
    }

    /* sieve is complete, count primes */
    int total = N >= 2 ? 1 : 0;
    //#pragma omp parallel for reduction(+:total)
    for (i = 1; i <= memorySize; i++)
    {
        total += isPrime[i];
    }

    return total;
}

int main(void)
{
    //int total = eratosthenesOdd(100, 1);
    int total = eratosthenesOdd(100);
    printf("Number of primes: %d\n", total);
    return 0;
}

And this output:

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Number of primes: 25

By inspection, this is correct for the primes up to 100.

Program to find prime numbers

You can do this faster using a nearly optimal trial division sieve in one (long) line like this:

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);

The approximation formula for number of primes used here is π(x) < 1.26 x / ln(x). We only need to test by primes not greater than x = sqrt(num).

Note that the sieve of Eratosthenes has much better run time complexity than trial division (should run much faster for bigger num values, when properly implemented).

Program that prints prime numbers

There are multiple problems in your code:

• the test for primality if (primeCheck(i, y) == 0) is incorrect: you should pass 2 as the first argument and i as the second.
• the loop should start at i = y and run while i >= x, decrementing i to find the largest primes in the range first.
• you should store the primes and stop when 2 have been found.
• the primality test function should be modified to return 1 if i > j to prevent infinite recursion on some inputs, such as primeCheck(2, 1).
• testing divisors up to and including sqrt(j) is sufficient in primeCheck(). You can stop the recursion when j < i * i, which can be tested without potential overflow as j / i < i.

Here is a modified version of your code:

#include <stdio.h>

int usersInput(int *x, int *y);
void swapping(int *x, int *y);
int primeCheck(int i, int j);

int main() {
    int x, y, i, num1, num2;
    
    if (!usersInput(&x, &y)) {
        return 1;
    }
    if (x > y) {
        swapping(&x, &y);
    }

    printf("The value of x is %d, and the value of y is %d.\n", x, y);

    for (i = y, num1 = num2 = 0; i >= x; i--) {
        if (primeCheck(2, i) == 0) {
            if (num2 == 0) {
                num2 = i;
            } else {
                num1 = i;
                break;
            }
        }
    }
    printf("The two largest prime numbers from %d to %d are: %.0d %.0d\n",
            x, y, num1, num2);
    return 0;
}

// read user input return zero on failure
int usersInput(int *x, int *y) {
    printf("Enter the value of x: ");
    if (scanf("%d", x) != 1)
       return 0;
    printf("Enter the value of y: ");
    return scanf("%d", y) == 1;
}

void swapping(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int primeCheck(int i, int j) {
    if (j < 2) {
        return 1;  // negative, 0 or 1: not prime
    } else if (j / i < i) {
        return 0;  // all factors tested up to sqrt(j): j is prime
    } else if (j % i == 0) {
        return 1;  // composite, not prime
    } else {
        return primeCheck(i + 1, j);
    }
}

Output:

Enter the value of x: 10
Enter the value of y: 3
The value of x is 3, and the value of y is 10.
The two largest prime numbers from 3 to 10 are: 5 7

my python program is to find prime numbers between two intervals but i am getting 9 in the output can you please tell what mistake i am doing

In case of 9, you're checking if the number is divisible by 2, it's not, and then you print the number and don't check anything else.

You're also looping till i+1, meaning you check if the number is divisible by itself, which it is...

Try changing those:

start = int(input('enter starting point of interval:'))
end = int(input('enter ending point of interval:'))
for i in range(start,end+1):
    if i>1:
        for j in range(2,i):
            if (i % j == 0):
                break
        else:
            print(i, end = " ")

Also, instead of checking if i>1 in every loop, change the loop conditions, and you can loop until the square root.

End result:

import math
start = int(input('enter starting point of interval:'))
end = int(input('enter ending point of interval:'))
for i in range(max(start, 2),end+1):
    if i % 2 == 0  and i != 2: continue
    if all((i%j!=0) for j in range(3,int(math.sqrt(i))+1, 2)):
        print(i, end = " ")

Program to find a specific prime number end in an infinite loop

You put x = 1, and then loop on a range starting from 2: so the for is never executed, and the while loops indefinitely. You need to start with x = 2, or to handle the special case of x = 1

EDIT
The code works for x at least 9: the for loop is never executed until int(math.sqrt(x)) is at least 3

Program to find Prime numbers. Chapter 2 Self test schildt java beginner's guide

Let's focus onto these for loops.

        for(i=2; i < 100; i++) {
            isprime = true;
            for (j=2; j <= i/j; j++)
                if((i%j) == О) isprime = false;
            if (isprime)
                System.out.println(i +" - is a prime number."); 
        }

The first loop iterates through all numbers you want to test. Easy enough to understand, it simply tells "I want to perform the following test on all numbers from 2 to 100".

for (j=2; j <= i/j; j++)
    if((i%j) == О) isprime = false;

Now this loop is pure math.
Mathematically, a prime number :

is a natural number greater than 1 that cannot be formed by
multiplying two smaller natural numbers.

(source : Wikipedia)

You therefore iterate through all numbers that, multiplied, would form i.

But do you really need to ?
If, as an example, i = 3*25, do you need to iterate all the way to 25 to know i is not a prime number ?

The answer is obviously no, since after testing for j=3, you already know i is composite.

Mathematically, multiple algorithms exist to check whether a number is prime or composite., but a reasonably correct way to do it is to check whether a number is a multiple of any number between 2 and its own square root. You are performing a rounded-up version of this.

Checking for all numbers between 2 and i is redundant for reasons cited above.

EDIT : Answer to 2)

When using

for (j=2; j <= i; j++)
    if((i%j) == 0) isprime = false;

you are telling the compiler to stop looping after performing the test on j==i. Of course, when j equals i, (i%j) == 0 always evaluates to true.

In non-informatical terms, you are checking whether a number is composed of any number, excluding 1, including itself, whereas you should check whether it is composed of any number, excluding 1 and itself.

This is due to Java's way of implementing for loops : they stop when the middle condition evaluates to false.

---

Related Topics