Jump to content

[Problem Solving #1] Deletable Primes

Problem #1 - Deletable Primes

 

So here's the first problem for a (hopefully) fun series of Problem Solving challenges! I solved a similar problem as a part of my introductory course to programming at University, so it shouldn't be too difficult.
 
Problem Description:
A Deletable Prime is a prime number from which you can remove digits one at a time, and each iteration of this removal gives you another prime.
 
Let's look at an example of a deletable prime: 
410256793 
4125679
4125673 
415673 
45673 
4567 
467 
6

All of the numbers above are prime, and deletable (by definition). 

It is worth noting that numbers such as: 
10859 
859 
59 

Are not Deletable Primes, because the removal of digit 1 implied the removal of digit 0 (10859 => 859), and thus it is not a valid sequence. 
Your objective is to find all of the Deletable Primes in range [0, 10000000], and output the number of Deletable Primes in that range, as well as their sum.

Input:
None.
 
Output:
Two lines. At the end of every line there must be a line break (\n).
The first line is the number of Deletable Primes existing in the interval [0, 10000000]. 
The second line is the sum of all of those Deletable Primes. 

Example Output (range [0, 10000]): 
699
3168960 
 
How to test your solution:
I have built a very simple web gateway. It is still very much in BETA, as it was developed in a few hours for this purpose.
The gateway has a listing of problems, and you create an account to submit your program's output to check if it is the correct solution to a given problem. The problem page there is also easier on the eyes than this thread's formatting (my bad!).
I chose this method because I don't like giving out the solution to problems, and it's fun because we can have a small gateway where we can check each other's stats. I'll be adding new features to the gateway eventually.
 
Without further ado, you can test your solution through the gateway located at this link. It is very simple to use, and I hope the community enjoys it.
The account creation process is very minimal, and your password is salt-hashed.
 
Final notes:

  • Create your account at the gateway with the same username as the one you use at the forums.
  • Include your code in spoiler tags, so that the thread isn't cluttered with code.
  • If you're having trouble solving the problem, ask the community for help! You may learn a lot from them.
  • Don't worry too much about efficiency if you're starting out. Solve the problem first, we'll then tell you how to improve it.
  • Please don't share the output solution if you've solved the problem.
  • If the problem description isn't clear, please ask for further explanation!

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

Well people with Dyscalculia are at a sever disadvantage.

The single biggest problem in communication is the illusion that it has taken place.

Link to comment
Share on other sites

Link to post
Share on other sites

Alright, a few tips. If you're a beginner, start by finding all of the primes in the interval [0, 10000000]. A simple, yet efficient enough for this, algorithm for that is the Sieve of Eratosthenes. It can easily be implemented using an array of booleans (preferably), and a loop.

Pseudo-code for a simple implementation:

boolean primes[10000000];boolean checked[10000000];for each integer i in [2, 9999999] dobegin   if not checked[i] then      prime[i] = true; //i is prime      for each integer k multiple of i < 10000000 do         checked[k] = true;end//after the main loop, you can check if a number is prime by accessing prime[n] and checking if it is true

Once you can check all of the primes in that interval, it is a matter of going through the numbers that are prime, and working on code to remove single digits from a number and testing those for primality. I can help with this part, but first try implementing the Sieve. :)

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

Imo Sieve of Atkin would be better.

Yes, it is more efficient. It is also less straightforward than the Sieve of Eratosthenes, so beginners will not find it as accessible. My post was directed at beginners.

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

Yes, it is more efficient. It is also less straightforward than the Sieve of Eratosthenes, so beginners will not find it as accessible. My post was directed at beginners.

 

I'm sorry, I meant no hostile overture hence why I did not quote you. I was intending to disseminate my own thoughts on the matter.

The single biggest problem in communication is the illusion that it has taken place.

Link to comment
Share on other sites

Link to post
Share on other sites

I'll drop another couple of hints; Multi-threading can be ones friend and if one also possesses a whopping great big GFX card then parallelism is available in the toolbox :D

The single biggest problem in communication is the illusion that it has taken place.

Link to comment
Share on other sites

Link to post
Share on other sites

A bit overkill for the problem but cuda ftw

#include "cuda_runtime.h"#include "device_launch_parameters.h"#include <cuda.h>#include <stdio.h>#include <iostream>cudaError_t calcDeletablePrimes(int *a, unsigned int size);__device__ bool isPrime(int x){    if(x == 2)    {        return true;    }    if(x == 1 || x % 2 == 0)    {        return false;    }    int sqroot = sqrt((float)x);    for(int i=3;i<=sqroot;i+=2)    {        if(x % i == 0)        {            return false;        }    }    return true;}__device__ bool isDeletable(int x){    if(!isPrime(x))    {        return false;    }    int numLength = 0;    int pos = 1;    while(x / pos >= 1)    {        pos *= 10;        numLength++;    }    if(numLength == 1)    {        return true;    }    for(int i=1;i<=numLength;++i)    {        int num;        if(i==1)        {            num = x / 10;        }        else if(i == numLength)        {            num = x % (int)pow((float)10,i-1);        }        else        {            int left = x / (int)pow((float)10,i);            int right = x % (int)pow((float)10,i-1);            num = left * (int)pow((float)10,i-1);            num += right;        }        int subNumLength = 0;        int subPos = 1;        while(num / subPos >= 1)        {            subPos *= 10;            subNumLength++;        }        if(subNumLength == numLength - 1)        {            if(isDeletable(num))            {                return true;            }        }    }    return false;}__global__ void deletablePrimes(int *out,int size){    int i = blockIdx.x * blockDim.x + threadIdx.x;    if(i >= size)    {        return;    }    if(isDeletable(i))    {        out[i] = i;    }    else    {        out[i] = 0;    }}int main(){    const int arraySize = 10000000;    //int array[arraySize];    int* array = new int[arraySize];    // Add vectors in parallel.    cudaError_t cudaStatus = calcDeletablePrimes(array, arraySize);    if (cudaStatus != cudaSuccess) {        fprintf(stderr, "error");        return 1;    }    unsigned long long sum = 0;    int numDeletable = 0;    for(int i=0;i<arraySize;++i)    {        if(array[i])        {            sum += array[i];            numDeletable += 1;        }    }    std::cout << numDeletable << std::endl;    std::cout << sum << std::endl;    // cudaDeviceReset must be called before exiting in order for profiling and    // tracing tools such as Nsight and Visual Profiler to show complete traces.    cudaStatus = cudaDeviceReset();    if (cudaStatus != cudaSuccess) {        fprintf(stderr, "cudaDeviceReset failed!");        return 1;    }    delete array;    getchar();    return 0;}// Helper function for using CUDA to add vectors in parallel.cudaError_t calcDeletablePrimes(int *a, unsigned int size){    int *dev_a = 0;    cudaError_t cudaStatus;    // Choose which GPU to run on, change this on a multi-GPU system.    cudaStatus = cudaSetDevice(0);    if (cudaStatus != cudaSuccess) {        fprintf(stderr, "cudaSetDevice failed!  Do you have a CUDA-capable GPU installed?");        goto Error;    }    /*    cudaStatus = cudaThreadSetLimit(cudaLimitStackSize,1024*4);    if(cudaStatus != cudaSuccess)    {        fprintf(stderr, "increasing stack size failed.");        goto Error;    }    */    cudaStatus = cudaMalloc((void**)&dev_a, size * sizeof(int));    if (cudaStatus != cudaSuccess) {        fprintf(stderr, "cudaMalloc failed!");        goto Error;    }    // Copy input vectors from host memory to GPU buffers.    cudaStatus = cudaMemcpy(dev_a, a, size * sizeof(int), cudaMemcpyHostToDevice);    if (cudaStatus != cudaSuccess) {        fprintf(stderr, "cudaMemcpy failed!");        goto Error;    }    // Launch a kernel on the GPU with one thread for each element.    int threadsPerBlock = 256;    int blocksPerGrid =(size + threadsPerBlock - 1) / threadsPerBlock;    deletablePrimes<<<blocksPerGrid, threadsPerBlock>>>(dev_a, size);    // Check for any errors launching the kernel    cudaStatus = cudaGetLastError();    if (cudaStatus != cudaSuccess) {        fprintf(stderr, "addKernel launch failed: %s\n", cudaGetErrorString(cudaStatus));        goto Error;    }        // cudaDeviceSynchronize waits for the kernel to finish, and returns    // any errors encountered during the launch.    cudaStatus = cudaDeviceSynchronize();    if (cudaStatus != cudaSuccess) {        fprintf(stderr, "cudaDeviceSynchronize returned error code %d after launching addKernel!\n", cudaStatus);        goto Error;    }    // Copy output vector from GPU buffer to host memory.    cudaStatus = cudaMemcpy(a, dev_a, size * sizeof(int), cudaMemcpyDeviceToHost);    if (cudaStatus != cudaSuccess) {        fprintf(stderr, "cudaMemcpy failed!");        goto Error;    }Error:    cudaFree(dev_a);        return cudaStatus;} 

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

A bit overkill for the problem but cuda ftw

 

Nice, you earn a cookie for solving it first! Interesting way to solve it, using CUDA.  :lol:

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

This makes the AP CS test look like a joke :P.

I'm going on vacation, so probably no time to take a crack at this in the next few days.

@wolfsinner would you mind making a sticky thread (PM a mod about making it sticky) or even a spoiler in your signature with links for each problem so people can review them? This seems like a really great endeavor and I don't want the programming challenges to fall into the bottomless pit of old threads, never to be found again.

[spoiler=My Current PC]AMD FX-8320 @ 4.2 Ghz | Xigmatek Dark Knight Night Hawk II | Gigabyte GA-990FXA-UD3 | 8GB Adata XPG V2 Silver 1600 Mhz RAM | Gigabyte 3X Windforce GTX 770 4GB @ 1.27 Ghz/7.25 Ghz | Rosewill Hive 550W Bronze PSU | Fractal Design Arc Midi R2 | Samsung Evo 250 GB SSD | Seagate Barracuda 1TB HDD | ASUS VS239H-P | Razer Deathadder 2013 Partlist

 

LTT Build-Off Thread: http://linustechtips.com/main/topic/35226-the-ltt-build-off-thread-no-building-required/

Link to comment
Share on other sites

Link to post
Share on other sites

This is where having dyscalculia as a programmer really hurts. Are they all going to be based on mathematics?

The single biggest problem in communication is the illusion that it has taken place.

Link to comment
Share on other sites

Link to post
Share on other sites

Nice, you earn a cookie for solving it first! Interesting way to solve it, using CUDA.  :lol:

Woo cookie.

Overall it would have been so much easier in something like Python and just converting to and from stings to remove digits
but I saw Nuluvius's comment about parallelism and figured ehh why not.

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

The initiative and this challenge are amazing! Keep the problems coming.

I am still working on a solution..

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

would you mind making a sticky thread (PM a mod about making it sticky) or even a spoiler in your signature with links for each problem so people can review them? This seems like a really great endeavor and I don't want the programming challenges to fall into the bottomless pit of old threads, never to be found again.

 

Will do, it would be great to have a sticky index of the problems. I'll add them to my signature once I release the second problem. Thanks a lot for the encouraging words.  :lol:

 

 

This is where having dyscalculia as a programmer really hurts. Are they all going to be based on mathematics?

 

When you mentioned Dyscalculia I didn't realize you were speaking of yourself. Sorry about that! Most problems will not be based on mathematics, so don't worry. I came up with this problem because the concept of Deletable Primes is perfect for an algorithm problem.

What part in particular are you having trouble with? Maybe we can help.

 

 

The initiative and this challenge are amazing! Keep the problems coming.

I am still working on a solution..

 

Awesome! Need any help, just ask.

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

nailed it! i feel quite satisfied now :P

i wonder @wolfsinner, should i share my solution or not? i thought i shouldn't, but well i see there's one posted already, so why not?

Link to comment
Share on other sites

Link to post
Share on other sites

nailed it! i feel quite satisfied now :P

i wonder @wolfsinner, should i share my solution or not? i thought i shouldn't, but well i see there's one posted already, so why not?

 

Nice! I think it's perfectly fine to share code, what I'd prefer people not sharing is the actual final output.

But it wouldn't be a proper discussion if we couldn't show off our work. It serves as proof.  :P

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

Nice! I think it's perfectly fine to share code, what I'd prefer people not sharing is the actual final output.

But it wouldn't be a proper discussion if we couldn't show off our work. It serves as proof.  :P

oh, i thought that by "solution" you meant the code!

 

alright then, here is my solution to the problem

the solution varies depending on the base choosen, so i made that a parameter, just in case

#include <stdio.h>#include <stdlib.h>#define N 10000000#define BASE 10typedef enum{    false,    true}bool;void sieve(bool* isPrime, size_t n){    size_t i, j;    isPrime[0] = isPrime[1] = false;    for(i = 2; i < n; i++)        isPrime[i] = true;    for(i = 2; i < n; i++)        if(isPrime[i])            for(j = 2 * i; j < n; j += i)                isPrime[j] = false;}size_t countDigits(int n){    if(n < BASE) return 1;    return 1 + countDigits(n / BASE);}int power(int base, int exp){    if(exp == 0) return 1;    int result = base;    while(--exp)        result *= base;    return result;}int removeDigit(size_t i, int n){    int factorA = power(BASE, i);    int factorB = power(BASE, i + 1);    int trunkA = (n / factorA) * factorA; // n = 123456, i = 3 ---> trunkA = 123000 (includes the digit to remove)    int trunkB = (n / factorB) * factorB; // n = 123456, i = 3 ---> trunkB = 120000 (excludes the digit to remove)    return trunkB / BASE + (n - trunkA);  // shifts trunkB one digit right, and adds the digits before the removed one}// isDelPrime is the array that tells you if a number is prime. this function turns it into an array that tells you if a number is a deletable prime, by excluding the primes that are not deletablevoid delSieve(bool* isDelPrime, size_t n){    size_t i, j, nDigits;    int newPrime, newPrimeLimit;    for(i = 0; i < n; i++)        if(isDelPrime[i]){ // if it's not prime, then it's not a deletable prime            nDigits = countDigits(i);            if(nDigits > 1){ // if it's prime and it's just one digit, then it's a deletable prime                isDelPrime[i] = false; // let's set to false the delete-primality of i, and test it again                newPrimeLimit = power(BASE, nDigits - 2); // needed to avoid the special case in which the leading zero gets removed                for(j = 0; j < nDigits; j++){                    newPrime = removeDigit(j, i);                    if(isDelPrime[newPrime] && newPrime >= newPrimeLimit)                        isDelPrime[i] = true;                }            }        }}int main(){    bool* isPrime = malloc(N * sizeof *isPrime);    sieve(isPrime, N);    delSieve(isPrime, N);    size_t i, nDelPrimes = 0;    long long sumDelPrimes = 0;    for(i = 0; i < N; i++)        if(isPrime[i]){            sumDelPrimes += i;            nDelPrimes++;        }    free(isPrime);    printf("%d\n%lld\n", nDelPrimes, sumDelPrimes);    return 0;}
Link to comment
Share on other sites

Link to post
Share on other sites

oh, i thought that by "solution" you meant the code!

 

alright then, here is my solution to the problem

the solution varies depending on the base choosen, so i made that a parameter, just in case

 

Very organized code. Your approach is very similar to mine, good job!

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

So I have setup a way to calculate all the primes under 10 000 000 but I do not really know how to check if a prime is a deletable prime. Could you maybe give some hints?

This is the code I have so far (java) :

And, do you have some tips for me on how to improve my code?

 

public class Main {	private static final int NUMBER = 10000000;	private static boolean[] isPrime = new boolean[NUMBER];	public static void main(String[] args){		sieve();		int numOfPrimes = 0;		long sumOfPrimes = 0;		for(int i = 0; i < isPrime.length; i++){			if(isPrime[i]){				numOfPrimes++; 				sumOfPrimes += i;			}		}		System.out.println(numOfPrimes);		System.out.println(sumOfPrimes);	}	/*	*	calculates the prime numbers	*/	private static void sieve(){		isPrime[0] = isPrime[1] = false;		for(int i = 2; i < NUMBER; i++)			isPrime[i] = true;		for(int i = 2; i < NUMBER; i++){			if(isPrime[i])				for(int j = 2 * i; j < NUMBER; j += i)					isPrime[j] = false;		}	}}

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

So I have setup a way to calculate all the primes under 10 000 000 but I do not really know how to check if a prime is a deletable prime. Could you maybe give some hints?

well, the definition of deletable prime involves removing digits from a number, so you can be pretty sure that you'll need a function that can do that

you can achieve that by either

- converting the number to a string, taking away a character, and then converting it back to a number

or

- finding some maths that remove a certain digit, which can be a bit tricky, but if you like playing with numbers it could be worth a shot

 

about the algorithm to find the deletable primes, try to do it with pen and paper first

the algorithm i chose is pretty much the same i would use if i had to do it manually

Link to comment
Share on other sites

Link to post
Share on other sites

well, the definition of deletable prime involves removing digits from a number, so you can be pretty sure that you'll need a function that can do that

you can achieve that by either

- converting the number to a string, taking away a character, and then converting it back to a number

or

- finding some maths that remove a certain digit, which can be a bit tricky, but if you like playing with numbers it could be worth a shot

about the algorithm to find the deletable primes, try to do it with pen and paper first

the algorithm i chose is pretty much the same i would use if i had to do it manually

Good, thank you. I will have another try when I wake up.

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


×