Problem 357

[mynameisalreadytaken]

Then you must either improve your code even more or you should check your algorithm for further improvements [using simple maths can save you a lot of computation time]. You could divide your Code into little pieces and check which one takes up the most time [or which one asymptotically needs the most time].


e.g.: Checking whether a number is prime by using trial division might be ok for small numbers, but as the numbers get bigger it's becoming very slow.

[kvom]

I haven't tried any Euler problems for a long time, but this one looked possible. My algorithm is very fast for all powers of 10, but my 10^8 answer is wrong. Can anyone verify that for 10^5, there are 87 numbers totaling 293145?

My last 10 numbers are:

7642
7702
8038
8110
8218
8542
8562
8962
9202
9718

If these are wrong, perhaps someone can give me a single number in that range so that I can check the algorithm.

[thundre]

Assuming you mean 10^4, your count and sum are both a little high. No mistakes in the last 10.

[MHLPlus]

My program return the answer for 10^6 after 25 seconds.I just have one question: Is it possible to say a number IS prime generating WITHOUT checking its divisor?

[mynameisalreadytaken]

In the thread for this Problem, one person actually made an algorithm that uses neither division nor modulo operations. However, it's not necessary to use this approach.

[mrb113]

I seem to be getting correct answers for smaller values of n (i.e. n = 100 instead of n = 100000000 as the problem specifies, but I am unsure.
Can anyone verify these answers?

For n = 30, the sum of all prime generating integers <= n = 71
For n = 100, the sum of all prime generating integers <= n = 401
For n = 1000, sum = 10695

Thanks!

[thundre]

Can anyone verify these answers?

The first two are OK, the last is wrong.

[Oliver1978]

I seem to be getting correct answers for smaller values of n (i.e. n = 100 instead of n = 100000000 as the problem specifies, but I am unsure.
Can anyone verify these answers?

For n = 30, the sum of all prime generating integers <= n = 71
For n = 100, the sum of all prime generating integers <= n = 401
For n = 1000, sum = 10695

Thanks!

I have 8427 for n = 1000, and 79601 for n = 5000.
Could this truly be true?

[nicolas.patrois]

It’s right.

[WickedCube]

Why isnt 1 included ?

[hk]

What makes you think it isn't?

[DoltBoy]

Love the problems in general. Some of my answers are incredibly clunky, with some not finishing after several hours. The longest one I've recently left to run for its entire time took about 20 minutes...

However, in the example given, I have noticed a glaring error. 30 is not one of the numbers. 2 is a divisor, 30+2 = 32, 32/2 = 16. 16 is NOT a prime... Don't know if it's worth bringing this to anyone's attention, but there it is. Apologies for pedantry.

Additionally, I have no clue what the process for pointing out errors is. Apologies if this is on the wrong thread.

[MuthuVeerappanR]

It's not (2+30)/2 but 2 + 30/2 = 2 + 15 = 17 is a prime..

The Bracket - Of - Divison - Multiplication - Addition - Subraction rule...

[hk]

Love the problems in general. Some of my answers are incredibly clunky, with some not finishing after several hours. The longest one I've recently left to run for its entire time took about 20 minutes...

However, in the example given, I have noticed a glaring error. 30 is not one of the numbers. 2 is a divisor, 30+2 = 32, 32/2 = 16. 16 is NOT a prime... Don't know if it's worth bringing this to anyone's attention, but there it is. Apologies for pedantry.

Additionally, I have no clue what the process for pointing out errors is. Apologies if this is on the wrong thread.

Problem 357 has been solved by 4326 members.
So you can assume that a multiple of 4326 members has read the problem carefully.
If there had been a glaring error in this wording it would have been noted long ago.
So if you think there is a glaring error in the wording chances are high that the error is yours.

[DoltBoy]

I said nothing about the wording being wrong. Nothing. I did, however, notice that the example chosen didn't work. Of the 4,326 people, how many actually looked at the example given and noticed an error? Maybe, like you, they speed-read what was there. (30+2)/2 =16. 16, as far as I'm aware, is NOT a prime number. Maybe I've muddled up my maths here. It's possible that 30 + 2 doesn't equate to 32. Or, if I'm correct there, it could be that 32 divided by 2 isn't, in actual fact, 16, and I've been lied to for many years by maths teachers. Maybe your definition of a prime is a number divisible by 2.

Please read what is being said, as opposed to assuming what you think is going to be said.

People look at the gist of the question, and solve it. Clearly, as you so aptly pointed out after failing so amazingly to read what I'd put in my comment, they are able to solve it because the definition of the problem is correct. I happened to notice that the example didn't fit the criteria applied in the definition of the problem!

Tl;dr - Wording is impeccable. Example doesn't fit for all given possibilities. 2 is one of the divisors in 30. 16 is not a prime number. (30+2)/2 = 16.

I refuse to apologise for being terse, as you clearly couldn't be bothered to read what I put.

[hk]

What MuthyVeerappanR tried to convey to you is that 2+30/2=2+(30/2)=2+15=17. And 17 is prime.
So the error is yours and not of the site.
So you're not terse but refusing to admit you were wrong, which is (please fill in an appropriate word here).

So for the last time: the example is correct.

[DoltBoy]

Ok, my apologies. For whatever reason, Muthu's response didn't show up when I looked. He's correct, I was confused, and your answer was out of context due to his response not being shown.

I was being an [insert vulgarity of choice], and am able to admit that.

[hk]

Apologies accepted. Happy solving.

[bodi]

Hello,

I would like to have the following result checked :

for n<10^7, the sum of prime generating numbers I get is : number removed

Thanks.

Bodi

[sjhillier]

Sorry Bodi, I think that number was wrong. I have removed it anyway to save misleading others.