Question Prime numbers and subtraction problem.

rideronix

New member
Joined
Nov 24, 2012
Messages
1
Programming Experience
Beginner
Hello everyone,


I'm currently working on a calculator and in order to challenge myself, I decided not to use any loops (while, for, ...) but only use recursive methods (if ... then ... return else return).


So basically what I'm trying to do is create a function that checks if the 2 numbers I've entered are primes numbers and if so, it subtract number A with number B. If the result is 6 then true, else false. A and B may not be greater than 1,000.


Here goes my code:


C#:
        static bool prime_6(int a, int B)/>/>
        {
            int x;
            x = 2; // this number will divide number a and b to check if they are prime numbs.
            
                if (a < 1000 && b < 1000) //setting an exception
                {
                    if (a % x != 0 && x < a) // Checking if number a is a prime number.
                    {
                    }
                    if (b % x != 0 && x < B)/>/> // Checking if number b is a prime number.
                    {
                        x++;                   // Adding +1 to x
                        return is_sexy(a, B)/>/>; // Launching back the function
                    }


                    return (a - b == 6); // Once it's done (if number a and b are prime, test if a - b = 6)
                }


                else
                {
                    return false; // Otherwise false
                
            }


        }


Now, I know some things I've done wrong: setting the "x=2" at the begining will always set my x to 2 and thus never ending the function but I don't see where to place it... any ideas ? Or improvement ? Or other mistakes ?


Thanks in advance.
 

AceInfinity

Member
Joined
Dec 1, 2012
Messages
5
Location
Canada
Programming Experience
10+
Here's my prime checking function:
C#:
private bool IsPrime(int input)
{
	if (input == 2) return true;
	else if (input == 1 || input % 2 == 0) return false;

	for (int n = 3; n < Math.Sqrt(input); n += 2)
	if (input % n == 0 && n != input) { return false; }

	return true;
}

First check both for not being greater than 1000. Then, check with the function and if both numbers return true from calling it, then subtract the numbers, and check the result for == 6... There's lots of ways the code above can be improved. Why did you choose recursion for this though? A for loop was sufficient enough and probably the better strategy anyways :)
 

DANILIN

Active member
Joined
Oct 19, 2018
Messages
42
Programming Experience
10+
Prime numbers are accelerated: root is removed from cycle
and it is possible to count a prime number by counting such
and such and it is found out:
in range of up to 1 million numbers: 78 thousand primes

C#:
using System; using System.Text; // PRIME_mult.cs DANILIN
namespace prime // rextester.com/VBXFL2777
{ class Program
    { static void Main(string[] args)
        { var start = DateTime.Now; int f=0; int j=2; int q=0;
            Random rand = new Random(); // long p = 2147483648-1;
            long p = rand.Next(Convert.ToInt32(Math.Pow(2, 22))-1);
            long s = Convert.ToInt32(Math.Pow(p,0.5));
            while (f < 1)
            { if (j >= s)
                { f=2; }
              if (p % j == 0)
              { q=1; Console.WriteLine("{0} {1} {2}",p,j,Convert.ToInt32(p/j));}
              j++;
            }
if (q != 1) { Console.WriteLine(«Prime {0} BillionS», p); }
var finish = DateTime.Now;
Console.WriteLine(finish — start);
Console.ReadKey();
}}}
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
6,511
Location
Chesapeake, VA
Programming Experience
10+
Again, you should be using meaningful variable names, and properly indenting your code.

What's the point of having f as an integer when you could simply have a boolean flag whether to continue looping or not?

What's the point of having q as an integer when you could simply have a boolean flag whether a factor of the target prime was found or not?

Why do you continue to loop around in the while loop when a factor was found?

Line 12 already tells you that there will be no remainder, why do you need to convert the result of p/j to an integer in line 13?
 

DANILIN

Active member
Joined
Oct 19, 2018
Messages
42
Programming Experience
10+
Conversion to a integer: against design of form "5.0"

Initially there were 3 states of flag f: ternary
0 = start & 1 = multiplier & 2 = prime
so flag is an ordinary integer

Now logic is: while flag f<1 reaches root
we check whether root has been reached
& then flag f=2 & exit

q flag is responsible for simplicity
because root is reached in all cases
& if root is reached without multipliers
then number is simple
 
Last edited:

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
6,511
Location
Chesapeake, VA
Programming Experience
10+
Initially there were 3 states of flag f: ternary
0 = start & 1 = multiplier & 2 = prime
so flag is an ordinary integer

Now logic is: while flag f<1 reaches root
we check whether root has been reached
& then flag f=2 & exit
But nowhere in your code is f assigned a value of 1.
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
6,511
Location
Chesapeake, VA
Programming Experience
10+
q flag is responsible for simplicity
because root is reached in all cases
& if root is reached without multipliers
then number is simple
A flag only needs 2 possible values. An integer can hold more than 2 possible values.
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
6,511
Location
Chesapeake, VA
Programming Experience
10+
Conversion to a integer: against design of form "5.0"
Since p and j are integer types (one is long and another is int), integer division will be used which will result in an integer type. There is no need to convert to integer.
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
6,511
Location
Chesapeake, VA
Programming Experience
10+
Oh! Oh! Your code thinks that 1 is prime. And it also thinks that 2 is not prime.
 

DANILIN

Active member
Joined
Oct 19, 2018
Messages
42
Programming Experience
10+
line 12:

if (p % j == 0 && f!=2)

now: 2 is prime
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
6,511
Location
Chesapeake, VA
Programming Experience
10+
A rewrite of the code in post #2 to fix some bugs seem simplest:
C#:
static bool IsPrime(int candidate)
{
    if (candidate <= 1)
        return false;

    if (candidate == 2)
        return true;

    if (candidate % 2 == 0)
        return false;

    int root = (int) Math.Sqrt(candidate);
    for(int factor = 3; factor <= root; factor += 2)
    {
        if (candidate % factor == 0)
            return false;
    }

    return true;
}
 
Top Bottom