Jump to content

[Problem Solving #1] Deletable Primes

It is still incorrect. Even with \n after each line (I still don't know if I am supposed to type \n after the line)

Type the first number, hit enter

type the second number, hit enter

click submit

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

It is still incorrect. Even with \n after each line (I still don't know if I am supposed to type \n after the line)

 

You're not. :P I'll remove your incorrect submissions. Do the following:

 

1. Manually write the count number there, and hit the return key (enter);

2. Manually write the sum number there, and hit the return key (enter);

3. Send.

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

You're not. :P I'll remove your incorrect submissions. Do the following:

 

1. Manually write the count number there, and hit the return key (enter);

2. Manually write the sum number there, and hit the return key (enter);

3. Send.

 

 

 

Type the first number, hit enter

type the second number, hit enter

click submit

 

Very good! Thank you for your help!

Maybe you should change the instructions for submitting a solution.. ? Or I am just stupid.. :P

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

Very good! Thank you for your help!

Maybe you should change the instructions for submitting a solution.. ? Or I am just stupid.. :P

 

Maybe I'll find a simpler format, but this is the format usually used in contest environments. :P

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

Ok it's not me I have just confirmed it by doing this in C. I get the same result each time across 3 different pieces of hardware, 2 different VMs, two different programming languages and 3 different code bases.

 

[OMITTED]
 
This is consistent. What does it mean?

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

 

 

Ok it's not me I have just confirmed it by doing this in C. I get the same result each time across 3 different pieces of hardware, 2 different VMs, two different programming languages and 3 different code bases.

 

[OMITTED]
 
This is consistent. What does it mean?

 

 

It means I was blind sided...

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

Yeah, computers tend to agree on the result of calculations

Anyway that's the correct answer, please edit it away

Maybe you're submitting it wrong in the form? Both lines must end with a newline char

Link to comment
Share on other sites

Link to post
Share on other sites

Yeah, computers tend to agree on the result of calculations

Anyway that's the correct answer, please edit it away

Maybe you're submitting it wrong in the form? Both lines must end with a newline char

 

Done now edit your quote of me :)

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

Done now edit your quote of me :)

i didn't think of that *facepalm*

Link to comment
Share on other sites

Link to post
Share on other sites

I was blind sided by getting obsessed that I still had the maths/logic wrong :/

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 was blind sided by getting obsessed that I still had the maths/logic wrong :/

it's ok, it's over now, you beat it :D

Link to comment
Share on other sites

Link to post
Share on other sites

  • 3 weeks later...

I'm working on it (a bit late but still). I got something figured out but it is slow as fuck :P So I'll see if I can improve it a bit then I'll submit :)

 

edit: I think I've got it working correctly now, lemme clean up my code a bit and I'll post it :)

Build log "Whiplash" : http://linustechtips.com/main/topic/158477-the-hero/

Whiplash: 4790k@4,4Ghz|Maximus VII Hero|4x4Gb Red/Black HyperX fury 1866Mhz|R9 290 Tri-X|Modded 450D|Sleeved cables on a M12II evo 850W|M500 480Gb| BenQ XL2411T@144Hz

Laptop: 4700MQ|16Gb@1600Mhz|Quadro 1100M|1080P|128Gb SSD|500Gb 7200RPM hdd

Link to comment
Share on other sites

Link to post
Share on other sites

Here my solution.

import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class DeletablePrimes {	public static void main(String[] args){		List<Integer> primes = primes(10000000);		List<Integer> deletablePrimes = new ArrayList<Integer>();		long sum = 0;		for(int i : primes){			if(isDeletablePrime(Integer.toString(i))){				deletablePrimes.add(i);				sum+=i;			}		}		System.out.println(deletablePrimes.size());		System.out.println(sum);	}	public static List<Integer> primes(int n){		int p = 2;		boolean[] primes_b = new boolean[n];		Arrays.fill(primes_b, true);		primes_b[0] = false;		primes_b[1] = false;		outerloop: while(p<n){			for(int x=2; p*x<n;x++){				primes_b[x*p] = false;			}				for(int i = 2; i<=primes_b.length;i++){				//selecting next p				try{					if(primes_b[i]){if(i>p){p=i;break;}}				}catch(IndexOutOfBoundsException e){					break outerloop;				}			}		}		List<Integer> primes = new ArrayList<Integer>();		for(int i =0;i<primes_b.length;i++){			if(primes_b[i]){primes.add(i);};		}		return primes;	}	public static boolean isprime(int num){		if(num < 2) return false;		if(num == 2 || num == 3) return true;		if(num%2 == 0 || num%3 == 0) return false;		long sqrtN = (long)Math.sqrt(num)+1;		for(long i = 6L; i <= sqrtN; i += 6) {			if(num%(i-1) == 0 || num%(i+1) == 0) return false;		}		return true;	}	public static boolean isDeletablePrime(String prime){		if(Integer.parseInt(prime.substring(0,1))==0){return false;};		if(prime.length()==1){			if(isprime(Integer.parseInt(prime))){				return true;			}else{				return false;			}		}		for(int r = 0; r<prime.length();r++){			String buffer = prime.substring(0,r)+prime.substring(r+1,prime.length());			if(isprime(Integer.parseInt(buffer))){				if(isDeletablePrime(buffer)){					return true;				}			}		}		return false;	}} 

Or pastebin: http://pastebin.com/2fKwvcwB

(I'm sorry for the derpy function/var names ^^)

 

This took me about 3 hours to get right and after that some time cleaning up my code ;). From those 3 hours I wasted like 1,5-2 hours figuring Java out again(looking up functions and stuff like that on the interwebs :P)(it has been more then I Year since I used Java ^^)

Note, I've never had any lessons in algorithmics or real lessons in coding (I've had some BASIC and Java at programming class but that didn't go further than let the program print the sum or product of two summitted integers). I'm all self tought untill this point. However, september I'm starting at Delft university to Computer science.

Build log "Whiplash" : http://linustechtips.com/main/topic/158477-the-hero/

Whiplash: 4790k@4,4Ghz|Maximus VII Hero|4x4Gb Red/Black HyperX fury 1866Mhz|R9 290 Tri-X|Modded 450D|Sleeved cables on a M12II evo 850W|M500 480Gb| BenQ XL2411T@144Hz

Laptop: 4700MQ|16Gb@1600Mhz|Quadro 1100M|1080P|128Gb SSD|500Gb 7200RPM hdd

Link to comment
Share on other sites

Link to post
Share on other sites

-snip-

 

Well at least you did far better than my epic string crunching approach. Nice work.

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

Haha thanks!

 

I also made a lot of stupid mistakes, I forgot for example the sum of all the deletable primes would be bigger then the max integer size so I was why the hell is the sum negative when I try n=10000000 but not when n=10000. ^^

Build log "Whiplash" : http://linustechtips.com/main/topic/158477-the-hero/

Whiplash: 4790k@4,4Ghz|Maximus VII Hero|4x4Gb Red/Black HyperX fury 1866Mhz|R9 290 Tri-X|Modded 450D|Sleeved cables on a M12II evo 850W|M500 480Gb| BenQ XL2411T@144Hz

Laptop: 4700MQ|16Gb@1600Mhz|Quadro 1100M|1080P|128Gb SSD|500Gb 7200RPM hdd

Link to comment
Share on other sites

Link to post
Share on other sites

So yeah, I worked on this when I had over 2 days w/o sleep and had just finished a 12-hr day at work (small break).

In that mental state, took about 40 minutes to write.

 

The basic idea behind it was to find deletable primes under each power of 10, from the bottom up, by seeing if any

primes in the range above the previously checked range contained any of the primes within that previously checked

range. Overall, probably very inefficient, as with a max value of 10,000,000 the program takes over an hour to

compute. Anyways, all 406 lines of code(C++) are in the spoiler below...

#include <vector>#include <iostream>using namespace std;int main(void) {	vector<int> primes;	vector<int> possPrimes;	vector<int> delPrimesUnder10;	vector<int> delPrimesUnder100;	vector<int> delPrimesUnder1000;	vector<int> delPrimesUnder10000;	vector<int> delPrimesUnder100000;	vector<int> delPrimesUnder1000000;	vector<int> delPrimesUnder10000000;	vector<bool> checked;	bool prime = false;	bool poss = false;	bool done = false;	bool fin;	int num = 0;	int temp = 0;	int pos = 0;	int arr[7];	int a[6];	const int size = 10000;	// Generate Primes	for(int i = 0; i < size; i++) {		checked.push_back(false);	}	primes.push_back(2);	primes.push_back(3);	for(int c = 5; c < size; c+=2) {		if(!checked[c]) {			prime = true;			for(int i = 3; i <= sqrt((float)c); i+=2) {				if((c%i) == 0) {					if(i != c)						prime = false;				}			}			if(prime) {				primes.push_back(c);				prime = false;				for(int x = 1; x < size/c; x++) {					checked[x*c] = true;				}			}		}	}	// Weed out primes that can't be Deletable (don't contain a 2, 3, 5, or 7).	for(int c = 0; c < primes.size(); c++) {		temp = primes[c];		poss = false;		done = false;		if(temp > 1000000)			num = 1000000;		else if(temp > 100000)			num = 100000;		else if(temp > 10000)			num = 10000;		else if(temp > 1000) 			num = 1000;		else if(temp > 100) 			num = 100;		else 			num = 10;		while(!done && !poss) {			if(temp/num == 2 || temp/num == 3 || temp/num == 5 || temp/num == 7) {				poss = true;			}			else {				temp = temp - (temp/num)*num;			}			if(num == 1) {				done = true;			}			num /= 10;		}		if(poss) {			possPrimes.push_back(primes[c]);		}	}	// Start finding Deletable Primes by working from bottom up.	for(int i = 0; i < possPrimes.size() && possPrimes[i] < 10; i++) {		delPrimesUnder10.push_back(possPrimes[i]);		pos++;	}	for(int i = pos; i < possPrimes.size() && possPrimes[i] < 100; i++) {		fin = false;		arr[0] = possPrimes[i]/10;		arr[1] = possPrimes[i] - 10*arr[0];		for(int x = 0; x < delPrimesUnder10.size() && !fin; x++) {			if(arr[0] == delPrimesUnder10[x] || arr[1] == delPrimesUnder10[x]) {				delPrimesUnder100.push_back(possPrimes[i]);				fin = true;			}		}		pos++;	}	for(int i = pos; i < possPrimes.size() && possPrimes[i] < 1000; i++) {		fin = false;		arr[0] = possPrimes[i]/100;		arr[1] = (possPrimes[i] - 100*arr[0])/10;		arr[2] = (possPrimes[i] - 100*arr[0] - 10*arr[1]);		for(int j = 0; j < delPrimesUnder100.size() && !fin; j++) {			a[0] = delPrimesUnder100[j]/10;			a[1] = delPrimesUnder100[j] - 10*a[0];			if(arr[0] == a[0] && arr[1] == a[1]) {				delPrimesUnder1000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[0] == a[0] && arr[2] == a[1]) {				delPrimesUnder1000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[1] == a[0] && arr[2] == a[1]) {				delPrimesUnder1000.push_back(possPrimes[i]);				fin = true;			}		}		pos++;	}	for(int i = pos; i < possPrimes.size() && possPrimes[i] < 10000; i++) {		fin = false;		arr[0] = possPrimes[i]/1000;		arr[1] = (possPrimes[i] - 1000*arr[0])/100;		arr[2] = (possPrimes[i] - 1000*arr[0] - 100*arr[1])/10;		arr[3] = (possPrimes[i] - 1000*arr[0] - 100*arr[1] - 10*arr[2]);		for(int j = 0; j < delPrimesUnder1000.size() && !fin; j++) {			a[0] = delPrimesUnder1000[j]/100;			a[1] = (delPrimesUnder1000[j] - 100*a[0])/10;			a[2] = (delPrimesUnder1000[j] - 100*a[0] - 10*a[1]);			if(arr[0] == a[0] && arr[1] == a[1] && arr[2] == a[2]) {				delPrimesUnder10000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[0] == a[0] && arr[1] == a[1] && arr[3] == a[2]) {				delPrimesUnder10000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[0] == a[0] && arr[2] == a[1] && arr[3] == a[2]) {				delPrimesUnder10000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[1] == a[0] && arr[2] == a[1] && arr[3] == a[2]) {				delPrimesUnder10000.push_back(possPrimes[i]);				fin = true;			}		}		pos++;	}	for(int i = pos; i < possPrimes.size() && possPrimes[i] < 100000; i++) {		fin = false;		arr[0] = possPrimes[i]/10000;		arr[1] = (possPrimes[i] - 10000*arr[0])/1000;		arr[2] = (possPrimes[i] - 10000*arr[0] - 1000*arr[1])/100;		arr[3] = (possPrimes[i] - 10000*arr[0] - 1000*arr[1] - 100*arr[2])/10;		arr[4] = (possPrimes[i] - 10000*arr[0] - 1000*arr[1] - 100*arr[2] - 10*arr[3]);		for(int j = 0; j < delPrimesUnder10000.size() && !fin; j++) {			a[0] = delPrimesUnder10000[j]/1000;			a[1] = (delPrimesUnder10000[j] - 1000*a[0])/100;			a[2] = (delPrimesUnder10000[j] - 1000*a[0] - 100*a[1])/10;			a[3] = (delPrimesUnder10000[j] - 1000*a[0] - 100*a[1] - 10*a[2]);			if(arr[0] == a[0] && arr[1] == a[1] && arr[2] == a[2] && arr[3] == a[3]) {				delPrimesUnder100000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[0] == a[0] && arr[1] == a[1] && arr[2] == a[2] && arr[4] == a[3]) {				delPrimesUnder100000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[0] == a[0] && arr[1] == a[1] && arr[3] == a[2] && arr[4] == a[3]) {				delPrimesUnder100000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[0] == a[0] && arr[2] == a[1] && arr[3] == a[2] && arr[4] == a[3]) {				delPrimesUnder100000.push_back(possPrimes[i]);				fin = true;			}			else if(arr[1] == a[0] && arr[2] == a[1] && arr[3] == a[2] && arr[4] == a[3]) {				delPrimesUnder100000.push_back(possPrimes[i]);				fin = true;			}		}		pos++;	}	for(int i = pos; i < possPrimes.size() && possPrimes[i] < 1000000; i++) {		fin = false;		arr[0] = possPrimes[i]/100000;		arr[1] = (possPrimes[i] - 100000*arr[0])/10000;		arr[2] = (possPrimes[i] - 100000*arr[0] - 10000*arr[1])/1000;		arr[3] = (possPrimes[i] - 100000*arr[0] - 10000*arr[1] - 1000*arr[2])/100;		arr[4] = (possPrimes[i] - 100000*arr[0] - 10000*arr[1] - 1000*arr[2] - 100*arr[3])/10;		arr[5] = (possPrimes[i] - 100000*arr[0] - 10000*arr[1] - 1000*arr[2] - 100*arr[3] - 10*arr[4]);		for(int j = 0; j < delPrimesUnder100000.size() && !fin; j++) {			a[0] = delPrimesUnder100000[j]/10000;			a[1] = (delPrimesUnder100000[j] - 10000*a[0])/1000;			a[2] = (delPrimesUnder100000[j] - 10000*a[0] - 1000*a[1])/100;			a[3] = (delPrimesUnder100000[j] - 10000*a[0] - 1000*a[1] - 100*a[2])/10;			a[4] = (delPrimesUnder100000[j] - 10000*a[0] - 1000*a[1] - 100*a[2] - 10*a[3]);			if(arr[0] == a[0]) {				if(arr[1] == a[1]) {					if(arr[2] == a[2] && arr[3] == a[3] && arr[4] == a[4]) {						delPrimesUnder1000000.push_back(possPrimes[i]);						fin = true;					}					else if(arr[2] == a[2] && arr[3] == a[3] && arr[5] == a[4]) {											delPrimesUnder1000000.push_back(possPrimes[i]);						fin = true;					}					else if(arr[2] == a[2] && arr[4] == a[3] && arr[5] == a[4]) {						delPrimesUnder1000000.push_back(possPrimes[i]);						fin = true;					}					else if(arr[3] == a[2] && arr[4] == a[3] && arr[5] == a[4]) {						delPrimesUnder1000000.push_back(possPrimes[i]);						fin = true;					}				}				else if(arr[2] == a[1] && arr[3] == a[2] && arr[4] == a[3] && arr[5] == a[4]) {					delPrimesUnder1000000.push_back(possPrimes[i]);					fin = true;				}			}			else if(arr[1] == a[0] && arr[2] == a[1] && arr[3] == a[2] && arr[4] == a[3] && arr[5] == a[4]) {				delPrimesUnder1000000.push_back(possPrimes[i]);				fin = true;			}		}		pos++;	}	for(int i = pos; i < possPrimes.size() && possPrimes[i] < 10000000; i++) {		fin = false;		arr[0] = possPrimes[i]/1000000;		arr[1] = (possPrimes[i] - 1000000*arr[0])/100000;		arr[2] = (possPrimes[i] - 1000000*arr[0] - 100000*arr[1])/10000;		arr[3] = (possPrimes[i] - 1000000*arr[0] - 100000*arr[1] - 10000*arr[2])/1000;		arr[4] = (possPrimes[i] - 1000000*arr[0] - 100000*arr[1] - 10000*arr[2] - 1000*arr[3])/100;		arr[5] = (possPrimes[i] - 1000000*arr[0] - 100000*arr[1] - 10000*arr[2] - 1000*arr[3] - 100*arr[4])/10;		arr[6] = (possPrimes[i] - 1000000*arr[0] - 100000*arr[1] - 10000*arr[2] - 1000*arr[3] - 100*arr[4] - 10*arr[5]);		for(int j = 0; j < delPrimesUnder1000000.size() && !fin; j++) {			a[0] = delPrimesUnder1000000[j]/100000;			a[1] = (delPrimesUnder1000000[j] - 100000*a[0])/10000;			a[2] = (delPrimesUnder1000000[j] - 100000*a[0] - 10000*a[1])/1000;			a[3] = (delPrimesUnder1000000[j] - 100000*a[0] - 10000*a[1] - 1000*a[2])/100;			a[4] = (delPrimesUnder1000000[j] - 100000*a[0] - 10000*a[1] - 1000*a[2] - 100*a[3])/10;			a[5] = (delPrimesUnder1000000[j] - 100000*a[0] - 10000*a[1] - 1000*a[2] - 100*a[3] - 10*a[4]);			if(arr[0] == a[0]) {				if(arr[1] == a[1]) {										if(arr[2] == a[2] && arr[3] == a[3] && arr[4] == a[4] && arr[5] == a[5]) {						delPrimesUnder10000000.push_back(possPrimes[i]);						fin = true;					}					else if(arr[2] == a[2] && arr[3] == a[3] && arr[4] == a[4] && arr[6] == a[5]) {						delPrimesUnder10000000.push_back(possPrimes[i]);						fin = true;					}					else if(arr[2] == a[2] && arr[3] == a[3] && arr[5] == a[4] && arr[6] == a[5]) {						delPrimesUnder10000000.push_back(possPrimes[i]);						fin = true;					}					else if(arr[2] == a[2] && arr[4] == a[3] && arr[5] == a[4] && arr[6] == a[5]) {						delPrimesUnder10000000.push_back(possPrimes[i]);						fin = true;					}					else if(arr[3] == a[2] && arr[4] == a[3] && arr[5] == a[4] && arr[6] == a[5]) {													delPrimesUnder10000000.push_back(possPrimes[i]);						fin = true;					}				}				else if(arr[2] == a[1] && arr[3] == a[2] && arr[4] == a[3] && arr[5] == a[4] && arr[6] == a[5]) {											delPrimesUnder10000000.push_back(possPrimes[i]);					fin = true;				}			}			else if(arr[1] == a[0] && arr[2] == a[1] && arr[3] == a[2] && arr[4] == a[3] && arr[5] == a[4] && arr[6] == a[5]) {				delPrimesUnder10000000.push_back(possPrimes[i]);				fin = true;			}		}	}	// Throw all DeletablePrimes into one vector. Find vector size and sum.	vector<int> delPrime;	for(int i = 0; i < delPrimesUnder10.size(); i++) {		delPrime.push_back(delPrimesUnder10[i]);	}	for(int i = 0; i < delPrimesUnder100.size(); i++) {		delPrime.push_back(delPrimesUnder100[i]);	}	for(int i = 0; i < delPrimesUnder1000.size(); i++) {		delPrime.push_back(delPrimesUnder1000[i]);	}	for(int i = 0; i < delPrimesUnder10000.size(); i++) {		delPrime.push_back(delPrimesUnder10000[i]);	}	for(int i = 0; i < delPrimesUnder100000.size(); i++) {		delPrime.push_back(delPrimesUnder100000[i]);	}	for(int i = 0; i < delPrimesUnder1000000.size(); i++) {		delPrime.push_back(delPrimesUnder1000000[i]);	}	for(int i = 0; i < delPrimesUnder10000000.size(); i++) {		delPrime.push_back(delPrimesUnder10000000[i]);	}	int numDelPrime = delPrime.size();	unsigned long long sumDelPrime = 0;	for(int i = 0; i < numDelPrime; i++) {		sumDelPrime += delPrime[i];	}		cout << "Number of Deletable Primes: " << numDelPrime << endl;	cout << "Sum of these primes: " << sumDelPrime << endl;	system("pause");}

CPU - FX 8320 @ 4.8 GHz

| MoBo - Sabertooth 990FX | GPU - XFX Radeon HD 7870 GHz Ed. @ 1.075 GHz | CPU Cooler - H100 | RAM - 16 GB Dual Channel Vengeance @ 1600 MHz (didn't care to push these...) | OS - Windows 8 Pro | Storage - OCZ Vertex 3 (120 GB Boot), Samsung 830 Pro 64 GB, WD Black 1 TB, some random 320 GB from a laptop | PSU - CM Silent Hybrid Pro 850W (MDPC Sleeving) | Case - 800D | Monitors - ASUS V238H/ X Star DP2710LED | Mouse - M90 Keyboard - CM Quickfire Rapid w/ custom key caps

"When life gives you lemons, Don't make lemonade, make life take the lemons back!" - Cave Johnson, CEO

Link to comment
Share on other sites

Link to post
Share on other sites

  • 2 months later...

Oh man I have no idea where I am going wrong lol.

Can someone verify that these are indeed deletable primes to which I am supposed to be looking for: http://www.mediafire.com/view/pojp1pat722qguo/delprimes.txt

The algorithm I have at the moment is ~50 lines and takes ~61,694ms (about a minute) to generate primes and sort out what I believe to be deletable primes although I am not sure if it is doing it correctly.

Could someone verify?

 

Thanks TizzyT

Link to comment
Share on other sites

Link to post
Share on other sites

Oh man I have no idea where I am going wrong lol.

Can someone verify that these are indeed deletable primes to which I am supposed to be looking for:http://www.mediafire...o/delprimes.txt

The algorithm I have at the moment is ~50 lines and takes ~61,694ms (about a minute) to generate primes and sort out what I believe to be deletable primes although I am not sure if it is doing it correctly.

Could someone verify?

 

Thanks TizzyT

mmm they look right to me

the number of primes is correct, the last few primes and the first few primes are correct too, so you should be good

be careful to put a line break after each of the two line when you submit your solution

Link to comment
Share on other sites

Link to post
Share on other sites

mmm they look right to me

the number of primes is correct, the last few primes and the first few primes are correct too, so you should be good

be careful to put a line break after each of the two line when you submit your solution

Is the line break parsed with "/n"? or is it by a combination of a character return and a line feed (Pressing Enter)?

 

Edit: Thanks BTW

Link to comment
Share on other sites

Link to post
Share on other sites

Is the line break parsed with "/n"? or is it by a combination of a character return and a line feed (Pressing Enter)?

i think that they both should work, but i usually go with manually pressing enter, so you should be safe using that method

Link to comment
Share on other sites

Link to post
Share on other sites

i think that they both should work, but i usually go with manually pressing enter, so you should be safe using that method

OHHH lol I need to press enter again for the second line as well.....FML all those "incorrect"s lol

Sorry

 

COMPLETE LACK OF ABILITY TO FOLLOW DIRECTIONS!!! lol my bad

 

 

Code: VB.net

Module DelPrimes    Sub Main()        Dim Primes As List(Of Integer) = Sieve(10000000)        Dim table(Primes(Primes.Count - 1)) As Boolean        Dim sum As Double = 17        For Each prime As Integer In Primes : table(prime) = True : Next        For i = 4 To Primes.Count - 1            If i > Primes.Count - 1 Then Exit For            Dim intString As String = Primes(i)            table(0) = False            For x = 0 To intString.Length - 1                Dim crnt As String = intString.Remove(x, 1)                If Not crnt.StartsWith("0") Then                    If table(crnt) = True Then                        table(0) = True                        Exit For                    End If                End If            Next            If table(0) = False Then                table(Primes(i)) = False                Primes.RemoveAt(i)                i -= 1            Else                sum += Primes(i)            End If        Next        Console.WriteLine(Primes.Count & vbCrLf & sum)        Console.ReadKey()    End Sub    Function Sieve(ByVal limit As Integer) As List(Of Integer)        Dim sqrt As Integer, CrntNbr = 11        Sieve = {2, 3, 5, 7}.ToList        While CrntNbr < limit            sqrt = Math.Sqrt(CrntNbr)            For Each prime In Sieve                If prime <= sqrt Then                    If CrntNbr Mod prime = 0 Then Exit For                Else                    Sieve.Add(CrntNbr)                    Exit For                End If            Next            CrntNbr += 2        End While    End FunctionEnd Module

 

Code: C#

using System;using System.Collections.Generic;namespace DeletablePrimesCSharp{    class DelPrimes    {        static void Main(string[] args)        {            List<int> Primes = Sieve(10000000);            bool[] Table = new bool[Primes[Primes.Count - 1] + 1];            double sum = 17;            foreach (int prime in Primes)            {                Table[prime] = true;            }            for (int i = 4; i <= Primes.Count - 1; i++)            {                if (i > Primes.Count - 1)                    break;                string intString = Convert.ToString(Primes[i]);                Table[0] = false;                for (int x = 0; x <= intString.Length - 1; x++)                {                    string crnt = intString.Remove(x, 1);                    if (!(crnt.StartsWith("0")))                    {                        if (Table[int.Parse(crnt)] == true)                        {                            Table[0] = true;                            break;                        }                    }                }                if (Table[0] == false)                {                    Table[Primes[i]] = false;                    Primes.RemoveAt(i);                    i--;                }                else                {                    sum += Primes[i];                }            }            Console.WriteLine(Primes.Count + System.Environment.NewLine + sum);            Console.ReadKey();        }        static List<int> Sieve(int limit)        {            List<int> Primes = new List<int> { 2, 3, 5, 7 };            int sqrt = 0;            int crntNbr = 11;            while (crntNbr < limit)            {                sqrt = (int)Math.Sqrt(crntNbr);                foreach (int prime in Primes)                {                    if (prime <= sqrt)                    {                        if (crntNbr % prime == 0)                            break;                    }                    else                    {                        Primes.Add(crntNbr);                        break;                    }                }                crntNbr += 2;            }            return Primes;        }    }}

Link to comment
Share on other sites

Link to post
Share on other sites

OHHH lol I need to press enter again for the second line as well.....FML all those "incorrect"s lol

 

I deleted the incorrect submissions since it was a matter of formatting. All problem results end with a line break, keep that in mind from now on. :P

 

Good job, I encourage you to keep going!

Want to solve problems? Check this out.

Link to comment
Share on other sites

Link to post
Share on other sites

I deleted the incorrect submissions since it was a matter of formatting. All problem results end with a line break, keep that in mind from now on. :P

 

Good job, I encourage you to keep going!

Thanks a lot but you didn't have to since it was my fault for being an idiot xD. Sorry about that will keep in mind for future submission and thanks again.

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;} 

I am interested in how much faster paralleling this stuff makes it, can you tell me the time this takes to complete, and what GPU you have.

Link to comment
Share on other sites

Link to post
Share on other sites

I am interested in how much faster paralleling this stuff makes it, can you tell me the time this takes to complete, and what GPU you have.

It takes ~.8 seconds with a 660ti as it was written in that post, which is about double what @Ciccioo 's solution takes. By using a sieve to calculate primes on the CPU then sending the rest of the problem to the GPU takes it down to about .4 seconds. It's not really a great problem for comparing parallel to serial because the serial algorithm is just so much more efficient than the parallel version because it takes advantage of previously calculated values.

1474412270.2748842

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


×