www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Prime number

reply Greatsam4sure <greatsam4sure gmail.com> writes:
I know D is very powerful from my little experience. What is the 
idiomatic way to get prime numbers say from 1-30 without using 
loops(outer and inner loop). Can map, filter, fold etc in 
algorithm be use.  Pls show some code with chain call.

I can easily achieve even numberd and odd numbers using filter. 
But prime numbers I have to use 2loops.

I will appreciate any help,just a newbie in D
Aug 02 2018
next sibling parent Dennis <dkorpel gmail.com> writes:
On Thursday, 2 August 2018 at 08:30:05 UTC, Greatsam4sure wrote:

 I know D is very powerful from my little experience. What is 
 the idiomatic way to get prime numbers say from 1-30 without 
 using loops(outer and inner loop). Can map, filter, fold etc in 
 algorithm be use.  Pls show some code with chain call.

 I can easily achieve even numberd and odd numbers using filter. 
 But prime numbers I have to use 2loops.

 I will appreciate any help,just a newbie in D


If you just want a small number of prime numbers and your goal is 
to make it a simple chain of range functions, I would do this:

```
import std.stdio: writeln;
import std.algorithm: filter, canFind;
import std.range: iota;

void main()
{
     auto isPrime = (int number) => number >= 2 && !iota(2, 
number).canFind!(x => (number % x) == 0);
     writeln(iota(30).filter!isPrime);
}

```

You first make a simple prime filter, and then apply it to a 
range of integers 0 to 30 using `iota(30)`.
I use lambda syntax for isPrime, but you can also make it an 
explicit function:
```
bool isPrime(int number) {
   return number >= 2 && !iota(2, number).canFind!(x => (number % 
x) == 0);
}
```

`iota(2, number)` generates a range of integers from 2 to 
`number` (excluding `number` itself), and with canFind we can see 
if any of those divide our number. If so, then number isn't prime.

Note that if you're serious about calculating primes, you should 
look for an efficient algorithm. Even in this naive algorithm 
there are many optimization possibilities, like stopping the iota 
at sqrt(number), but it would make the range code more 
complicated.
Aug 02 2018
prev sibling next sibling parent reply Cym13 <cpicard openmailbox.org> writes:
On Thursday, 2 August 2018 at 08:30:05 UTC, Greatsam4sure wrote:

 I know D is very powerful from my little experience. What is 
 the idiomatic way to get prime numbers say from 1-30 without 
 using loops(outer and inner loop). Can map, filter, fold etc in 
 algorithm be use.  Pls show some code with chain call.

 I can easily achieve even numberd and odd numbers using filter. 
 But prime numbers I have to use 2loops.

 I will appreciate any help,just a newbie in D


Denis' answer is good but I'd like to add that the idiomatic D 
solution is to use whatever tool is the most adequate to solve 
the issue. If two loops is more natural it wouldn't make much 
sense to force yourself to use range functions (even though I'd 
obviously understand that stand to learn to use them).
Aug 02 2018
parent reply Greatsam4sure <greatsam4sure gmail.com> writes:
On Thursday, 2 August 2018 at 09:35:20 UTC, Cym13 wrote:

 On Thursday, 2 August 2018 at 08:30:05 UTC, Greatsam4sure wrote:

 I know D is very powerful from my little experience. What is 
 the idiomatic way to get prime numbers say from 1-30 without 
 using loops(outer and inner loop). Can map, filter, fold etc 
 in algorithm be use.  Pls show some code with chain call.

 I can easily achieve even numberd and odd numbers using 
 filter. But prime numbers I have to use 2loops.

 I will appreciate any help,just a newbie in D


 Denis' answer is good but I'd like to add that the idiomatic D 
 solution is to use whatever tool is the most adequate to solve 
 the issue. If two loops is more natural it wouldn't make much 
 sense to force yourself to use range functions (even though I'd 
 obviously understand that stand to learn to use them).




Thanks, I like the idea of using helper function from algorithm 
module to do the magic instead of loops.  I want to know How To 
optimize it to efficient.
I will appreciate any help.
I will also appreciate a link to a comprehensive tutorial on the 
algorithm module. The documentation did not give me all the help 
I needed
Aug 02 2018
parent Cym13 <cpicard openmailbox.org> writes:
On Thursday, 2 August 2018 at 14:37:56 UTC, Greatsam4sure wrote:

 On Thursday, 2 August 2018 at 09:35:20 UTC, Cym13 wrote:

 On Thursday, 2 August 2018 at 08:30:05 UTC, Greatsam4sure 
 wrote:

 I know D is very powerful from my little experience. What is 
 the idiomatic way to get prime numbers say from 1-30 without 
 using loops(outer and inner loop). Can map, filter, fold etc 
 in algorithm be use.  Pls show some code with chain call.

 I can easily achieve even numberd and odd numbers using 
 filter. But prime numbers I have to use 2loops.

 I will appreciate any help,just a newbie in D


 Denis' answer is good but I'd like to add that the idiomatic D 
 solution is to use whatever tool is the most adequate to solve 
 the issue. If two loops is more natural it wouldn't make much 
 sense to force yourself to use range functions (even though 
 I'd obviously understand that stand to learn to use them).




 Thanks, I like the idea of using helper function from algorithm 
 module to do the magic instead of loops.  I want to know How To 
 optimize it to efficient.
 I will appreciate any help.


Computing prime numbers efficiently would require something more 
complex like an Atkin sieve which I doubt will be very easy to 
implement without loop.

That said, to start optimizing without changing the algorithm you 
can profile your code with -profile to see where you're spending 
time that you can shave off and rewrite the code to accelerate 
those parts. You should really start by changing the algorithm 
though.


 I will also appreciate a link to a comprehensive tutorial on 
 the algorithm module. The documentation did not give me all the 
 help I needed


Not specifically on the algorithm module but I'd recommend 
reading [1] for a good intro to D from basics to advanced topics.

For algorithms especially, I'd recommend reading on templates [2] 
and ranges [3].

Especially one thing you should know to understand the concepts 
behind most range-based functions is that most of them try to 
work on infinite sequences of things and therefore make 
assumptions only about the first items and never about the last 
ones. That's why functions like std.algorithm.find don't just 
return the element or its position but the sub-sequence starting 
at that element. There are exceptions though, and this comment 
may not make much sense at first so feel free to ignore it for 
the moment, but hopefully it'll come back to you when you need it.

[1]: https://ddili.org/ders/d.en/index.html
[2]: https://ddili.org/ders/d.en/templates.html
[3]: https://ddili.org/ders/d.en/ranges.html
Aug 06 2018
prev sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 2 August 2018 at 08:30:05 UTC, Greatsam4sure wrote:

 I know D is very powerful from my little experience. What is 
 the idiomatic way to get prime numbers say from 1-30 without 
 using loops(outer and inner loop). Can map, filter, fold etc in 
 algorithm be use.  Pls show some code with chain call.

 I can easily achieve even numberd and odd numbers using filter. 
 But prime numbers I have to use 2loops.

 I will appreciate any help,just a newbie in D


you can cheat and download d_primes from dub :)
Aug 02 2018