Trying to divide a number by an array's elements, to check if it's prime (kinda)-CodePudding

My goal is for the user to enter a number, the program to divide it with each element from an array and then say if the number is prime or not.
This is the best I have come so far:

Console.Write("Enter a number: ");
int number = Convert.ToInt32(Console.ReadLine());

int i = 0;
int[] div = {1, 2, 3, 5, 7, 11 };
int result;


do
{
    result = number / div[i];
    i  ;
} while ((result % 1) == 0);

if ((result % 1) != 0)
{
    Console.WriteLine("The number seems to be prime for now");
    Console.ReadLine();
}

I know there's a problem but I can't figure it out. Also I might change the code, based on my progress and research.

CodePudding user response：

When you get stuck on a programming problem, break it into parts.

First, write a function that can tell you if a number is divisible by another number.

bool IsDivisibleBy(int dividend, int divisor)
{
    return (dividend % divisor) == 0;
}

Now write a function that will accept a list of divisors and do the same thing.

bool IsDivisibleByAny(int dividend, int[] divisors)
{
    foreach (var divisor in divisors)
    {
        bool isDivisible = IsDivisibleBy(dividend, divisor);
        if (isDivisible) return true;
    }
    return false;
}

Or one line with Linq (if you have gotten that far yet):

bool IsDivisibleByAny(int dividend, IEnumerable<int> divisors) =>
    divisors.Any( divisor => IsDivisibleBy(dividend, divisor) );

Now your main program is very easy to write:

var divisors = new int[] { 1, 2, 3, 5, 7, 11 };
Console.Write("Enter a number: ");
int number = Convert.ToInt32(Console.ReadLine());
bool isDivisible = IsDivisibleByAny(number, divisors);
if (!isDivisible)
{
    Console.WriteLine("The number seems to be prime for now");
}

CodePudding user response：

This will probably not be the answer you expect.

If we discard the first number (1), it seems your array div is a (very) partial list of primes. If you already know the prime numbers, you could simply check if the number entered is in that list. If yes it is a prime number.

While it could look like cheating, it is actually a widely used technique (calculating sinus/cosinus in signal processors for instance).

That could be implemented in several ways.

As a Linq query:

int Candidate; // The variable in which you store the read number.

var Primes = new List<int> { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, [...]}; // Could be obtained by parsing an external file.

var IsPrime = Primes.Any(p => p == Candidate);

Or for better computational efficiency, in a HashSet (a not so often used data structure. It could be replaced by the widely used Dictionary):

int Candidate; // The variable in which you store the read number.

var Primes = new HashSet<int> { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, [...]}; // Could be obtained by parsing an external file.

var IsPrime = Primes.ContainsKey(Candidate);

If you need a file with prime numbers, see https://primes.utm.edu/lists/small/millions/

You'll notice the interesting comment on the page:

In this directory I have the first fifty million primes in blocks of one million. Usually it is faster to run a program on your own computer than to download them, but by popular demand, here they are!

I hope it will motivate you to find how he does!

This leads to another path: actually calculate if a number is prime, but then your div array should not contains all these values (because you want to calculate then, right?).

This is another subject altogether, and I won't extend on this. For the record, the first known way to calculate the prime numbers was the Erastothenes' sieve.

See: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Notice than checking if a number is prime and calculating primes is a different problem (even if the first can be deduced by solving the second).

A last comment:

The two general methods I outlined: referring to an already computed list, and calculating, are good examples of tradeoffs.

the first one generally requires a large amount of memory, for very little computation power.
the second one might require a smaller amount of memory, but trading it for a large computation power.

In the case of prime number, neither tradeoff seems evidently better than the other, but in the the sinus/cosinus case I mentioned previously, using already computed values is tremendously advantageous, because of the cyclic nature of these functions. You only need a finite amount of memory space to store all the needed values. (assuming you don't need an infinite precision of course).